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 |
|
|
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 |