oj.uz

Submission #25781

# Submission time Handle Problem Language Result Execution time Memory
25781 2017-06-24T06:14:39 Z 서규호(#1081) 전압 (JOI14_voltage) C++14
45 / 100
 279 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);
	}
	for(int i=1; i<=N; i++){
		if(check[i]) continue;
		bipartite = true;
		color[i] = 1;
		dfs(i);
		if(!bipartite){
			cnt++;
		}
	}
	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;
		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);
                       ^

Subtask #1
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 3 ms 6412 KB Output is correct
5 Correct 0 ms 6412 KB Output is correct
6 Correct 0 ms 6544 KB Output is correct
7 Correct 0 ms 6412 KB Output is correct
8 Incorrect 3 ms 6412 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 11156 KB Output is correct
2 Correct 153 ms 12972 KB Output is correct
3 Correct 66 ms 11156 KB Output is correct
4 Correct 153 ms 13936 KB Output is correct
5 Correct 9 ms 7004 KB Output is correct
6 Correct 126 ms 11840 KB Output is correct
7 Correct 126 ms 14948 KB Output is correct
8 Correct 153 ms 14952 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 11156 KB Output is correct
2 Correct 66 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 106 ms 11964 KB Output is correct
6 Correct 116 ms 10500 KB Output is correct
7 Correct 189 ms 12376 KB Output is correct
8 Correct 166 ms 13404 KB Output is correct
9 Correct 159 ms 13180 KB Output is correct
10 Correct 123 ms 12180 KB Output is correct
11 Correct 133 ms 10500 KB Output is correct
12 Correct 99 ms 11472 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 11664 KB Output is correct
2 Correct 96 ms 14952 KB Output is correct
3 Correct 6 ms 6412 KB Output is correct
4 Correct 173 ms 12908 KB Output is correct
5 Correct 169 ms 13676 KB Output is correct
6 Correct 136 ms 12760 KB Output is correct
7 Correct 256 ms 13364 KB Output is correct
8 Correct 243 ms 13840 KB Output is correct
9 Correct 239 ms 12428 KB Output is correct
10 Correct 279 ms 14292 KB Output is correct
11 Correct 226 ms 12616 KB Output is correct
12 Correct 266 ms 14320 KB Output is correct
13 Incorrect 193 ms 12368 KB Output isn't correct
14 Halted 0 ms 0 KB -