oj.uz

Submission #129836

# Submission time Handle Problem Language Result Execution time Memory
129836 2019-07-13T10:20:18 Z onjo0127 전압 (JOI14_voltage) C++11
100 / 100
 176 ms 17320 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 5 ms 2808 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 5 ms 2808 KB Output is correct
5 Correct 5 ms 2728 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 2760 KB Output is correct
9 Correct 5 ms 2808 KB Output is correct
10 Correct 5 ms 2808 KB Output is correct
11 Correct 6 ms 2780 KB Output is correct
12 Correct 6 ms 2808 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7920 KB Output is correct
2 Correct 149 ms 12924 KB Output is correct
3 Correct 69 ms 8064 KB Output is correct
4 Correct 118 ms 14556 KB Output is correct
5 Correct 11 ms 3576 KB Output is correct
6 Correct 115 ms 10940 KB Output is correct
7 Correct 156 ms 16120 KB Output is correct
8 Correct 112 ms 16172 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 7536 KB Output is correct
2 Correct 53 ms 16160 KB Output is correct
3 Correct 53 ms 16248 KB Output is correct
4 Correct 4 ms 2684 KB Output is correct
5 Correct 93 ms 11228 KB Output is correct
6 Correct 85 ms 8440 KB Output is correct
7 Correct 85 ms 11848 KB Output is correct
8 Correct 98 ms 13560 KB Output is correct
9 Correct 86 ms 13180 KB Output is correct
10 Correct 93 ms 11592 KB Output is correct
11 Correct 79 ms 8440 KB Output is correct
12 Correct 102 ms 10384 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 9068 KB Output is correct
2 Correct 80 ms 17320 KB Output is correct
3 Correct 6 ms 3320 KB Output is correct
4 Correct 102 ms 12920 KB Output is correct
5 Correct 102 ms 14128 KB Output is correct
6 Correct 95 ms 12536 KB Output is correct
7 Correct 151 ms 13948 KB Output is correct
8 Correct 169 ms 14812 KB Output is correct
9 Correct 167 ms 12536 KB Output is correct
10 Correct 176 ms 15480 KB Output is correct
11 Correct 152 ms 12920 KB Output is correct
12 Correct 176 ms 15688 KB Output is correct
13 Correct 137 ms 12144 KB Output is correct
14 Correct 159 ms 16476 KB Output is correct
15 Correct 151 ms 15720 KB Output is correct
16 Correct 133 ms 14952 KB Output is correct
17 Correct 138 ms 12920 KB Output is correct
18 Correct 118 ms 12920 KB Output is correct