Submission #57691


Source Code Expand

#include <cstdio>
#include <vector>

using namespace std;

const int kUnvisited = 0;
const int kVisiting = 1;
const int kVisited = 2;

class Graph
{
public:
    explicit Graph(int n) : n_(n), m_(n * (n - 1) / 2), vis_(n),
                            adj_(n, vector<int>(n, 1))
    {
        for (int i = 0; i < n; i++) {
            adj_[i][i] = 0;
        }
    }

    void flip(int i, int j)
    {
        if (adj_[i][j]) {
            adj_[i][j] = adj_[j][i] = 0; --m_;
        } else {
            adj_[i][j] = adj_[j][i] = 1; ++m_;
        }
    }

    bool has_loop()
    {
        if (m_ >= n_) return false;

        fill(vis_.begin(), vis_.end(), kUnvisited);
        for (int i = 0; i < n_; i++) {
            if (!visit(i, -1)) return false;
        }
        return true;
    }

private:
    bool visit(int i, int src)
    {
        if (vis_[i] != kUnvisited) {
            return vis_[i] == kVisited;
        }
        vis_[i] = kVisiting;
        for (int j = 0; j < n_; j++) {
            if (j != src && adj_[i][j] && !visit(j, i)) return false;
        }
        vis_[i] = kVisited;
        return true;
    }

private:
    int n_, m_;
    vector<int> vis_;
    vector< vector<int> > adj_;
};

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    if (n >= 500) {
        for (int i = 0; i < m; i++) {
            puts("no");
        }
        return 0;
    }

    Graph g(n);
    for (int i = 0; i < m; i++) {
        int s, t;
        scanf("%d%d", &s, &t);
        --s, --t;
        g.flip(s, t);
        puts(g.has_loop() ? "yes" : "no");
    }

    return 0;
}

Submission Info

Submission Time
Task C - 森ですか?
User yuizumi
Language C++ (G++ 4.6.4)
Score 50
Code Size 1671 Byte
Status TLE
Exec Time 2033 ms
Memory 1852 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:64:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:76:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result

Set Name Easy All
Score / Max Score 50 / 50 0 / 50
Status
AC × 37
AC × 66
TLE × 13
Set Name Test Cases
Easy easy_01_00.txt, easy_01_01.txt, easy_01_02.txt, easy_01_03.txt, easy_01_04.txt, easy_02_00.txt, easy_02_01.txt, easy_02_02.txt, easy_02_03.txt, easy_02_04.txt, easy_03_00.txt, easy_03_01.txt, easy_03_02.txt, easy_03_03.txt, easy_03_04.txt, easy_04_00.txt, easy_04_01.txt, easy_04_02.txt, easy_04_03.txt, easy_04_04.txt, easy_05_00.txt, easy_05_01.txt, easy_05_02.txt, easy_05_03.txt, easy_05_04.txt, easy_06_00.txt, easy_06_01.txt, easy_06_02.txt, easy_06_03.txt, easy_06_04.txt, easy_07_00.txt, easy_07_01.txt, easy_07_02.txt, easy_07_03.txt, easy_07_04.txt, easy_08_00.txt, easy_08_01.txt
All easy_01_00.txt, easy_01_01.txt, easy_01_02.txt, easy_01_03.txt, easy_01_04.txt, easy_02_00.txt, easy_02_01.txt, easy_02_02.txt, easy_02_03.txt, easy_02_04.txt, easy_03_00.txt, easy_03_01.txt, easy_03_02.txt, easy_03_03.txt, easy_03_04.txt, easy_04_00.txt, easy_04_01.txt, easy_04_02.txt, easy_04_03.txt, easy_04_04.txt, easy_05_00.txt, easy_05_01.txt, easy_05_02.txt, easy_05_03.txt, easy_05_04.txt, easy_06_00.txt, easy_06_01.txt, easy_06_02.txt, easy_06_03.txt, easy_06_04.txt, easy_07_00.txt, easy_07_01.txt, easy_07_02.txt, easy_07_03.txt, easy_07_04.txt, easy_08_00.txt, easy_08_01.txt, hard_01_00.txt, hard_01_01.txt, hard_01_02.txt, hard_01_03.txt, hard_01_04.txt, hard_02_00.txt, hard_02_01.txt, hard_02_02.txt, hard_02_03.txt, hard_02_04.txt, hard_03_00.txt, hard_03_01.txt, hard_03_02.txt, hard_03_03.txt, hard_03_04.txt, hard_04_00.txt, hard_04_01.txt, hard_04_02.txt, hard_04_03.txt, hard_04_04.txt, hard_05_00.txt, hard_05_01.txt, hard_05_02.txt, hard_05_03.txt, hard_05_04.txt, hard_06_00.txt, hard_06_01.txt, hard_06_02.txt, hard_06_03.txt, hard_06_04.txt, hard_07_00.txt, hard_07_01.txt, hard_07_02.txt, hard_07_03.txt, hard_07_04.txt, hard_08_00.txt, hard_08_01.txt, hard_09_00.txt, hard_09_01.txt, hard_09_02.txt, hard_09_03.txt, hard_09_04.txt
Case Name Status Exec Time Memory
easy_01_00.txt AC 21 ms 600 KB
easy_01_01.txt AC 19 ms 812 KB
easy_01_02.txt AC 20 ms 780 KB
easy_01_03.txt AC 18 ms 784 KB
easy_01_04.txt AC 19 ms 792 KB
easy_02_00.txt AC 19 ms 812 KB
easy_02_01.txt AC 19 ms 784 KB
easy_02_02.txt AC 19 ms 776 KB
easy_02_03.txt AC 19 ms 784 KB
easy_02_04.txt AC 20 ms 692 KB
easy_03_00.txt AC 19 ms 788 KB
easy_03_01.txt AC 19 ms 776 KB
easy_03_02.txt AC 19 ms 788 KB
easy_03_03.txt AC 19 ms 788 KB
easy_03_04.txt AC 19 ms 684 KB
easy_04_00.txt AC 19 ms 788 KB
easy_04_01.txt AC 19 ms 780 KB
easy_04_02.txt AC 19 ms 780 KB
easy_04_03.txt AC 19 ms 784 KB
easy_04_04.txt AC 19 ms 788 KB
easy_05_00.txt AC 19 ms 664 KB
easy_05_01.txt AC 19 ms 784 KB
easy_05_02.txt AC 19 ms 692 KB
easy_05_03.txt AC 19 ms 808 KB
easy_05_04.txt AC 18 ms 784 KB
easy_06_00.txt AC 19 ms 784 KB
easy_06_01.txt AC 19 ms 788 KB
easy_06_02.txt AC 19 ms 796 KB
easy_06_03.txt AC 19 ms 780 KB
easy_06_04.txt AC 19 ms 792 KB
easy_07_00.txt AC 19 ms 784 KB
easy_07_01.txt AC 19 ms 780 KB
easy_07_02.txt AC 19 ms 816 KB
easy_07_03.txt AC 19 ms 784 KB
easy_07_04.txt AC 19 ms 696 KB
easy_08_00.txt AC 19 ms 788 KB
easy_08_01.txt AC 20 ms 668 KB
hard_01_00.txt AC 61 ms 1712 KB
hard_01_01.txt AC 64 ms 1336 KB
hard_01_02.txt AC 62 ms 1460 KB
hard_01_03.txt AC 61 ms 1084 KB
hard_01_04.txt AC 60 ms 1084 KB
hard_02_00.txt AC 20 ms 904 KB
hard_02_01.txt AC 22 ms 912 KB
hard_02_02.txt AC 24 ms 1040 KB
hard_02_03.txt AC 23 ms 1052 KB
hard_02_04.txt AC 25 ms 908 KB
hard_03_00.txt AC 245 ms 1460 KB
hard_03_01.txt AC 107 ms 1200 KB
hard_03_02.txt AC 287 ms 1588 KB
hard_03_03.txt AC 234 ms 1464 KB
hard_03_04.txt AC 370 ms 1720 KB
hard_04_00.txt AC 188 ms 1340 KB
hard_04_01.txt AC 23 ms 952 KB
hard_04_02.txt AC 53 ms 892 KB
hard_04_03.txt AC 21 ms 912 KB
hard_04_04.txt AC 59 ms 1040 KB
hard_05_00.txt AC 1079 ms 1840 KB
hard_05_01.txt TLE 2028 ms 1208 KB
hard_05_02.txt TLE 2027 ms 1592 KB
hard_05_03.txt TLE 2028 ms 1852 KB
hard_05_04.txt AC 1248 ms 1724 KB
hard_06_00.txt AC 36 ms 1596 KB
hard_06_01.txt AC 20 ms 792 KB
hard_06_02.txt AC 54 ms 1848 KB
hard_06_03.txt AC 959 ms 1048 KB
hard_06_04.txt TLE 2033 ms 1080 KB
hard_07_00.txt AC 745 ms 1720 KB
hard_07_01.txt TLE 2028 ms 1720 KB
hard_07_02.txt TLE 2028 ms 1464 KB
hard_07_03.txt TLE 2028 ms 1712 KB
hard_07_04.txt TLE 2028 ms 1720 KB
hard_08_00.txt AC 193 ms 1720 KB
hard_08_01.txt AC 62 ms 1716 KB
hard_09_00.txt TLE 2028 ms 1456 KB
hard_09_01.txt TLE 2028 ms 1340 KB
hard_09_02.txt TLE 2028 ms 1208 KB
hard_09_03.txt TLE 2027 ms 1328 KB
hard_09_04.txt TLE 2028 ms 1204 KB
sample1.txt AC 19 ms 772 KB
sample2.txt AC 20 ms 792 KB