# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
129714 | 2019-07-13T05:30:11 Z | 이온조(#3139) | 전압 (JOI14_voltage) | C++14 | 205 ms | 15020 KB |
#include <bits/stdc++.h> using namespace std; vector<int> adj[100009]; int O[100009], E[100009], D[100009], K, ans; bool vs[100009], chk[100009], root[100009]; void dfs(int x, int d, int p) { vs[x] = 1; D[x] = d; for(auto& it: adj[x]) { if(vs[it]) { if(D[it] > D[x]) continue; if(it == p) { p = -1; continue; } // printf("BACK edge: %d -- %d\n", x, it); if(D[x] - D[it] & 1) ++E[x], --E[it]; else ++O[x], --O[it], ++K; } else { // printf("TREE edge: %d -- %d\n", x, it); dfs(it, d+1, x); } } } void cal(int x) { chk[x] = 1; for(auto& it: adj[x]) if(!chk[it]) { cal(it); O[x] += O[it]; E[x] += E[it]; } if(!root[x] && O[x] == K && E[x] == 0) ++ans; } int main() { int N, M; scanf("%d%d",&N,&M); for(int i=0; i<M; i++) { int u, v; scanf("%d%d",&u,&v); adj[u].push_back(v); adj[v].push_back(u); } for(int i=1; i<=N; i++) if(!vs[i]) { dfs(i, 0, -1); root[i] = 1; } for(int i=1; i<=N; i++) if(!chk[i]) cal(i); if(K == 1) ++ans; printf("%d", ans); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 2808 KB | Output is correct |
2 | Correct | 4 ms | 2680 KB | Output is correct |
3 | Correct | 4 ms | 2680 KB | Output is correct |
4 | Correct | 4 ms | 2780 KB | Output is correct |
5 | Correct | 5 ms | 2808 KB | Output is correct |
6 | Correct | 5 ms | 2808 KB | Output is correct |
7 | Correct | 5 ms | 2808 KB | Output is correct |
8 | Correct | 5 ms | 2808 KB | Output is correct |
9 | Correct | 5 ms | 2812 KB | Output is correct |
10 | Correct | 5 ms | 2808 KB | Output is correct |
11 | Correct | 5 ms | 2808 KB | Output is correct |
12 | Correct | 5 ms | 2808 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 53 ms | 6764 KB | Output is correct |
2 | Correct | 100 ms | 11612 KB | Output is correct |
3 | Correct | 51 ms | 6796 KB | Output is correct |
4 | Correct | 110 ms | 13404 KB | Output is correct |
5 | Correct | 10 ms | 3452 KB | Output is correct |
6 | Correct | 83 ms | 9720 KB | Output is correct |
7 | Correct | 101 ms | 14968 KB | Output is correct |
8 | Correct | 114 ms | 15020 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 33 ms | 6768 KB | Output is correct |
2 | Correct | 52 ms | 14968 KB | Output is correct |
3 | Correct | 51 ms | 14988 KB | Output is correct |
4 | Correct | 4 ms | 2680 KB | Output is correct |
5 | Correct | 63 ms | 10208 KB | Output is correct |
6 | Correct | 75 ms | 7288 KB | Output is correct |
7 | Correct | 92 ms | 10744 KB | Output is correct |
8 | Correct | 96 ms | 12408 KB | Output is correct |
9 | Correct | 92 ms | 12152 KB | Output is correct |
10 | Correct | 95 ms | 10436 KB | Output is correct |
11 | Correct | 71 ms | 7288 KB | Output is correct |
12 | Correct | 86 ms | 9124 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 58 ms | 7528 KB | Output is correct |
2 | Correct | 81 ms | 14968 KB | Output is correct |
3 | Correct | 5 ms | 3320 KB | Output is correct |
4 | Correct | 91 ms | 11640 KB | Output is correct |
5 | Correct | 93 ms | 12816 KB | Output is correct |
6 | Correct | 103 ms | 11256 KB | Output is correct |
7 | Correct | 179 ms | 11768 KB | Output is correct |
8 | Correct | 176 ms | 12644 KB | Output is correct |
9 | Correct | 153 ms | 10360 KB | Output is correct |
10 | Correct | 159 ms | 13196 KB | Output is correct |
11 | Correct | 137 ms | 10568 KB | Output is correct |
12 | Correct | 161 ms | 13236 KB | Output is correct |
13 | Correct | 135 ms | 9928 KB | Output is correct |
14 | Correct | 160 ms | 14156 KB | Output is correct |
15 | Correct | 205 ms | 13316 KB | Output is correct |
16 | Correct | 145 ms | 12708 KB | Output is correct |
17 | Correct | 143 ms | 10516 KB | Output is correct |
18 | Correct | 124 ms | 10424 KB | Output is correct |