oj.uz

Submission #129713

# Submission time Handle Problem Language Result Execution time Memory
129713 2019-07-13T05:28:00 Z 이온조(#3139) 전압 (JOI14_voltage) C++14
45 / 100
 113 ms 15124 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];

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(x != 1 && 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);
		assert(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);
	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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Incorrect 4 ms 2680 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 6796 KB Output is correct
2 Correct 113 ms 11688 KB Output is correct
3 Correct 59 ms 6892 KB Output is correct
4 Correct 102 ms 13308 KB Output is correct
5 Correct 11 ms 3448 KB Output is correct
6 Correct 86 ms 9664 KB Output is correct
7 Correct 109 ms 15028 KB Output is correct
8 Correct 111 ms 15124 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 6808 KB Output is correct
2 Correct 53 ms 15084 KB Output is correct
3 Correct 52 ms 14968 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 66 ms 10104 KB Output is correct
6 Correct 103 ms 7312 KB Output is correct
7 Correct 88 ms 10744 KB Output is correct
8 Correct 107 ms 12612 KB Output is correct
9 Correct 98 ms 12024 KB Output is correct
10 Correct 95 ms 10380 KB Output is correct
11 Correct 78 ms 7288 KB Output is correct
12 Correct 97 ms 9136 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 7528 KB Output is correct
2 Correct 80 ms 15032 KB Output is correct
3 Incorrect 6 ms 3192 KB Output isn't correct
4 Halted 0 ms 0 KB -