oj.uz

Submission #129714

# Submission time Handle Problem Language Result Execution time Memory
129714 2019-07-13T05:30:11 Z 이온조(#3139) 전압 (JOI14_voltage) C++14
100 / 100
 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

voltage.cpp: In function 'void dfs(int, int, int)':
voltage.cpp:18:12: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
    if(D[x] - D[it] & 1) ++E[x], --E[it];
       ~~~~~^~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:39:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int N, M; scanf("%d%d",&N,&M);
            ~~~~~^~~~~~~~~~~~~~
voltage.cpp:41:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 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

Subtask #2
10.0 / 10.0

# 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

Subtask #3
35.0 / 35.0

# 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

Subtask #4
45.0 / 45.0

# 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