oj.uz

Submission #25771

# Submission time Handle Problem Language Result Execution time Memory
25771 2017-06-24T05:44:31 Z 서규호(#1081) 전압 (JOI14_voltage) C++14
10 / 100
 133 ms 13360 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,cnt1;
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]){
			if((lev[x]-lev[i])%2 == 0){
				cnt0++;
				ans = abs(lev[x]-lev[i])+1;
			}else{
				cnt1++;
				ans = M-abs(lev[x]-lev[i])-1;
			}
		}else{
			lev[i] = lev[x]+1;
			par[i] = x;
			dfs2(i);
		}
	}
}

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);
	printf("%d\n",ans);

	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:58: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:61: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 Incorrect 3 ms 5632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 9348 KB Output is correct
2 Correct 119 ms 11384 KB Output is correct
3 Correct 76 ms 9348 KB Output is correct
4 Correct 133 ms 12352 KB Output is correct
5 Correct 9 ms 6060 KB Output is correct
6 Correct 96 ms 10188 KB Output is correct
7 Correct 129 ms 13360 KB Output is correct
8 Correct 126 ms 13360 KB Output is correct

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 9348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 83 ms 10376 KB Output isn't correct
2 Halted 0 ms 0 KB -