oj.uz

Submission #25779

# Submission time Handle Problem Language Result Execution time Memory
25779 2017-06-24T06:07:30 Z 서규호(#1081) 전압 (JOI14_voltage) C++14
55 / 100
 173 ms 15708 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];

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){
	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);
		}
	}
}
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 == 1) 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 = 1;
	for(int i=1; i<=N; i++){
		if(check[i]) continue;
		bipartite = true;
		color[i] = 1;
		dfs(i);
		if(!bipartite){
			it = i;
			cnt++;
		}
	}
	if(cnt >= 2){
		puts("0");
		return 0;
	}
	for(int i=1; i<=N; i++) check[i] = false;
	dfs2(it);
	for(int i=1; i<=N; i++) check[i] = false;
	dfs3(it);
	if(cnt0[0] == 2) ans++;
	printf("%d\n",ans);

	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:74: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:77: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
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 0 ms 6412 KB Output is correct
7 Correct 0 ms 6412 KB Output is correct
8 Correct 0 ms 6412 KB Output is correct
9 Correct 0 ms 6412 KB Output is correct
10 Correct 0 ms 6412 KB Output is correct
11 Correct 3 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 39 ms 10128 KB Output is correct
2 Correct 79 ms 13064 KB Output is correct
3 Correct 46 ms 10128 KB Output is correct
4 Correct 146 ms 14352 KB Output is correct
5 Correct 6 ms 6892 KB Output is correct
6 Correct 116 ms 11472 KB Output is correct
7 Correct 153 ms 15708 KB Output is correct
8 Correct 159 ms 15708 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10128 KB Output is correct
2 Correct 59 ms 15700 KB Output is correct
3 Correct 46 ms 15704 KB Output is correct
4 Correct 0 ms 6412 KB Output is correct
5 Correct 123 ms 11900 KB Output is correct
6 Correct 126 ms 9712 KB Output is correct
7 Correct 73 ms 12272 KB Output is correct
8 Correct 159 ms 13640 KB Output is correct
9 Correct 126 ms 13352 KB Output is correct
10 Correct 103 ms 12008 KB Output is correct
11 Correct 129 ms 9712 KB Output is correct
12 Correct 173 ms 11060 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 11156 KB Output is correct
2 Correct 103 ms 15708 KB Output is correct
3 Incorrect 3 ms 6412 KB Output isn't correct
4 Halted 0 ms 0 KB -