oj.uz

Submission #25782

# Submission time Handle Problem Language Result Execution time Memory
25782 2017-06-24T06:30:47 Z 서규호(#1081) 전압 (JOI14_voltage) C++14
100 / 100
 283 ms 14952 KB 
#include <bits/stdc++.h>

#define lld long long
#define pp pair<int,int>
#define pb push_back
#define MOD 1000000007
#define left lleft
#define right rright
#define INF 2000000000
#define Linf 1000000000000000000LL
#define next nnext
#define minus mminus

using namespace std;

int N,M,ans;
int cnt,cnt0[100002],cnt1[100002];
int color[100002],lev[100002],par[100002];
bool check[100002];
vector<int> edge[100002],tmp;

bool bipartite;
void dfs(int x){
	check[x] = true;
	for(auto &i : edge[x]){
		if(color[i] == color[x]){
			bipartite = false;
		}else color[i] = 3-color[x];
		if(check[i]) continue;
		dfs(i);
	}
}
void dfs2(int x){
	tmp.pb(x);
	check[x] = true;
	int tcnt = 0;
	for(auto &i : edge[x]){
		if(tcnt == 0 && i == par[x]){
			tcnt = 1;
			continue;
		}
		if(check[i]){
			int t1,t2;
			t1 = x; t2 = i;
			if(lev[t1] > lev[t2]) swap(t1,t2);
			if((lev[t2]-lev[t1])%2 == 0){
				cnt0[t2]++;
				cnt0[t1]--;
				cnt0[0]++;
			}else{
				cnt1[t2]++;
				cnt1[t1]--;
				cnt1[0]++;
			}
		}else{
			lev[i] = lev[x]+1;
			par[i] = x;
			dfs2(i);
		}
	}
}
int root;
void dfs3(int x){
	check[x] = true;
	for(auto &i : edge[x]){
		if(check[i]) continue;
		dfs3(i);
		cnt0[x] += cnt0[i];
		cnt1[x] += cnt1[i];
	}
	if(cnt0[x] != cnt0[0] || x == root) return;
	if(cnt1[x] == 0) ans++;
}

int main(){
	scanf("%d %d",&N,&M);
	for(int i=1; i<=M; i++){
		int x,y;
		scanf("%d %d",&x,&y);
		edge[x].pb(y);
		edge[y].pb(x);
	}
	int it;
	for(int i=1; i<=N; i++){
		if(check[i]) continue;
		bipartite = true;
		color[i] = 1;
		dfs(i);
		if(!bipartite){
			cnt++;
			it = i;
		}
	}
	if(cnt >= 2){
		puts("0");
		return 0;
	}
	for(int i=1; i<=N; i++) check[i] = false;
	for(int i=1; i<=N; i++){
		if(check[i]) continue;
		if(cnt == 1 && i != it) continue;
		root = i;
		cnt0[0] = cnt1[0] = 0;
		tmp.clear();
		dfs2(i);
		for(auto &j : tmp) check[j] = false;
		dfs3(i);
		if(cnt0[0] == 2) ans++;
	}
	printf("%d\n",ans);

	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:76:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
voltage.cpp:79:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
                       ^
voltage.cpp:101:15: warning: 'it' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(cnt == 1 && i != it) continue;
               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6412 KB Output is correct
2 Correct 0 ms 6412 KB Output is correct
3 Correct 0 ms 6412 KB Output is correct
4 Correct 0 ms 6412 KB Output is correct
5 Correct 0 ms 6412 KB Output is correct
6 Correct 3 ms 6544 KB Output is correct
7 Correct 3 ms 6412 KB Output is correct
8 Correct 0 ms 6412 KB Output is correct
9 Correct 3 ms 6412 KB Output is correct
10 Correct 0 ms 6412 KB Output is correct
11 Correct 0 ms 6412 KB Output is correct
12 Correct 0 ms 6412 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11156 KB Output is correct
2 Correct 153 ms 12972 KB Output is correct
3 Correct 69 ms 11156 KB Output is correct
4 Correct 143 ms 13940 KB Output is correct
5 Correct 6 ms 7004 KB Output is correct
6 Correct 119 ms 11840 KB Output is correct
7 Correct 156 ms 14948 KB Output is correct
8 Correct 149 ms 14952 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11156 KB Output is correct
2 Correct 53 ms 14948 KB Output is correct
3 Correct 43 ms 14952 KB Output is correct
4 Correct 0 ms 6412 KB Output is correct
5 Correct 116 ms 11968 KB Output is correct
6 Correct 126 ms 10500 KB Output is correct
7 Correct 179 ms 12380 KB Output is correct
8 Correct 166 ms 13400 KB Output is correct
9 Correct 139 ms 13184 KB Output is correct
10 Correct 179 ms 12180 KB Output is correct
11 Correct 113 ms 10500 KB Output is correct
12 Correct 83 ms 11464 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 11664 KB Output is correct
2 Correct 89 ms 14948 KB Output is correct
3 Correct 0 ms 6412 KB Output is correct
4 Correct 156 ms 12912 KB Output is correct
5 Correct 153 ms 13676 KB Output is correct
6 Correct 159 ms 12756 KB Output is correct
7 Correct 259 ms 13364 KB Output is correct
8 Correct 223 ms 13840 KB Output is correct
9 Correct 239 ms 12428 KB Output is correct
10 Correct 243 ms 14296 KB Output is correct
11 Correct 246 ms 12612 KB Output is correct
12 Correct 283 ms 14324 KB Output is correct
13 Correct 156 ms 12372 KB Output is correct
14 Correct 253 ms 14880 KB Output is correct
15 Correct 266 ms 14340 KB Output is correct
16 Correct 209 ms 14124 KB Output is correct
17 Correct 126 ms 12384 KB Output is correct
18 Correct 176 ms 13108 KB Output is correct