Submission #129836

#	Time	Username	Problem	Language	Result	Execution time	Memory
129836		onjo0127	전압 (JOI14_voltage)	C++11	100 / 100	176 ms	17320 KiB

voltage

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45