oj.uz

Submission #156095

# Submission time Handle Problem Language Result Execution time Memory
156095 2019-10-03T09:11:36 Z HungAnhGoldIBO2020 전압 (JOI14_voltage) C++14
100 / 100
 144 ms 18808 KB 
#include<iostream>
#include<vector>
#include<algorithm>
const int N=2e5+2;
using namespace std;
vector<int> adj[N],lis1;
int cnt[N][3],color[N],level[N],numno=0,ans=0;
vector<pair<int,int> > lis;
bool used[N];
bool dfs(int x,bool valid){
	bool scare=valid,cac;
	for(int i=0;i<adj[x].size();i++){
		if(!color[adj[x][i]]){
			color[adj[x][i]]=3-color[x];
			if(scare){
				scare=dfs(adj[x][i],scare);
			}
			else{
				cac=dfs(adj[x][i],scare);	
			}
		}
		else{
			if(color[adj[x][i]]!=3-color[x]){
				scare=false;
			}
		}
	}
	return scare;
}
void dfs1(int x,int p){
	lis1.push_back(x);
	bool first=true;
	for(int i=0;i<adj[x].size();i++){
		if(!used[adj[x][i]]){
			used[adj[x][i]]=true;
			level[adj[x][i]]=level[x]+1;
			dfs1(adj[x][i],x);
			cnt[x][0]+=cnt[adj[x][i]][0];
			cnt[x][1]+=cnt[adj[x][i]][1];
		}
		else{
			if(adj[x][i]==p){
				if(first){
					first=false;
					continue;
				}
			}
			if(level[adj[x][i]]>level[x]){
				continue;
			}
			if((level[x]-level[adj[x][i]])%2==0){
				numno++;
				cnt[x][0]++;
				cnt[adj[x][i]][0]--;
			}
			else{
				cnt[x][1]++;
				cnt[adj[x][i]][1]--;
			}
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,i,j,k,root=0;
	cin>>n>>m;
	for(i=1;i<=m;i++){
		cin>>j>>k;
		lis.push_back({min(j,k),max(j,k)});
		adj[j].push_back(k);
		adj[k].push_back(j);
	}
	bool cac;
	for(i=1;i<=n;i++){
		if(!color[i]){
			color[i]=1;
			cac=dfs(i,true);
			if(!cac){
				if(!root){
					root=i;
				}
				else{
					cout<<0;
					return 0;
				}
			}
		}
	}
	if(!root){
		for(i=1;i<=n;i++){
			if(!used[i]){
				lis1.clear();
				used[i]=true;
				dfs1(i,i);
				for(j=0;j<lis1.size();j++){
					if(lis1[j]!=i&&cnt[lis1[j]][1]==0){
						ans++;
					}
				}
			}
		}
		cout<<ans;
		return 0;
	}
	used[root]=true;
	dfs1(root,root);
	if(numno==1){
		ans++;
	}
	for(i=1;i<=n;i++){
		if(i!=root&&used[i]&&cnt[i][0]==numno&&cnt[i][1]==0){
			ans++;
		}
	}
	cout<<ans;
}

Compilation message

voltage.cpp: In function 'bool dfs(int, bool)':
voltage.cpp:12:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
voltage.cpp:11:19: warning: variable 'cac' set but not used [-Wunused-but-set-variable]
  bool scare=valid,cac;
                   ^~~
voltage.cpp: In function 'void dfs1(int, int)':
voltage.cpp:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:96:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<lis1.size();j++){
             ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 11112 KB Output is correct
2 Correct 85 ms 15648 KB Output is correct
3 Correct 57 ms 11224 KB Output is correct
4 Correct 92 ms 16976 KB Output is correct
5 Correct 13 ms 6004 KB Output is correct
6 Correct 77 ms 14060 KB Output is correct
7 Correct 82 ms 18256 KB Output is correct
8 Correct 83 ms 18284 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11116 KB Output is correct
2 Correct 53 ms 18256 KB Output is correct
3 Correct 53 ms 18156 KB Output is correct
4 Correct 6 ms 5112 KB Output is correct
5 Correct 67 ms 13800 KB Output is correct
6 Correct 75 ms 12012 KB Output is correct
7 Correct 84 ms 14824 KB Output is correct
8 Correct 84 ms 16104 KB Output is correct
9 Correct 115 ms 15852 KB Output is correct
10 Correct 94 ms 14444 KB Output is correct
11 Correct 84 ms 12028 KB Output is correct
12 Correct 77 ms 13548 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 13412 KB Output is correct
2 Correct 82 ms 18808 KB Output is correct
3 Correct 8 ms 5624 KB Output is correct
4 Correct 84 ms 15468 KB Output is correct
5 Correct 82 ms 16556 KB Output is correct
6 Correct 92 ms 15340 KB Output is correct
7 Correct 134 ms 16484 KB Output is correct
8 Correct 140 ms 17180 KB Output is correct
9 Correct 127 ms 15332 KB Output is correct
10 Correct 144 ms 17772 KB Output is correct
11 Correct 130 ms 15552 KB Output is correct
12 Correct 136 ms 17764 KB Output is correct
13 Correct 103 ms 14184 KB Output is correct
14 Correct 126 ms 18532 KB Output is correct
15 Correct 140 ms 17892 KB Output is correct
16 Correct 128 ms 17224 KB Output is correct
17 Correct 124 ms 15332 KB Output is correct
18 Correct 114 ms 15460 KB Output is correct