oj.uz

Submission #156080

# Submission time Handle Problem Language Result Execution time Memory
156080 2019-10-03T08:08:12 Z HungAnhGoldIBO2020 전압 (JOI14_voltage) C++14
0 / 100
 158 ms 22432 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define int long long
const int inf=1e9+7;
const int N=2e5+2;
using namespace std;
vector<int> adj[N];
int cnt[N][2],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],valid);
			}
			else{
				cac=dfs(adj[x][i],valid);	
			}
		}
		else{
			if(color[adj[x][i]]!=3-color[x]){
				scare=false;
			}
		}
	}
	return scare;
}
void dfs1(int x,int p){
	bool first=true,first1=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(level[adj[x][i]]>level[x]){
				continue;
			}
			if(adj[x][i]==p){
				if(first){
					first=false;
				}
				else{
					cnt[x][0]+=inf;
					cnt[p][0]-=inf;
				}
				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,l,root=0,cnt1=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);
	}
	sort(lis.begin(),lis.end());
	for(i=0;i<lis.size();i++){
		if(i!=lis.size()-1&&lis[i].first==lis[i+1].first&&lis[i].second==lis[i+1].second){
			cnt1+=2;
			i++;
			continue;
		}
		if(i>0&&lis[i].first==lis[i-1].first&&lis[i].second==lis[i-1].second){
			cnt1++;
			continue;
		}
	}
	bool cac;
	for(i=1;i<=n;i++){
		if(!color[i]){
			//cout<<i<<endl;
			color[i]=1;
			cac=dfs(i,true);
			if(!cac){
				if(!root){
					root=i;
				}
				else{
//					cout<<"cac"<<endl;
					cout<<0;
					return 0;
				}
			}
		}
	}
	if(!root){
		cout<<m-cnt1;
		return 0;
	}
	used[root]=true;
	dfs1(root,root);
	if(numno==1){
		ans++;
	}
	for(i=1;i<=n;i++){
		//cout<<i<<' '<<cnt[i][0]<<' '<<cnt[i][1]<<endl;
		if(i!=root&&used[i]&&cnt[i][0]==numno&&cnt[i][1]==0){
			ans++;
		}
	}
	cout<<ans;
}

Compilation message

voltage.cpp: In function 'bool dfs(long long int, bool)':
voltage.cpp:14:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
voltage.cpp:13:19: warning: variable 'cac' set but not used [-Wunused-but-set-variable]
  bool scare=valid,cac;
                   ^~~
voltage.cpp: In function 'void dfs1(long long int, long long int)':
voltage.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
voltage.cpp:33:18: warning: unused variable 'first1' [-Wunused-variable]
  bool first=true,first1=true;
                  ^~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:80:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<lis.size();i++){
          ~^~~~~~~~~~~
voltage.cpp:81:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i!=lis.size()-1&&lis[i].first==lis[i+1].first&&lis[i].second==lis[i+1].second){
      ~^~~~~~~~~~~~~~
voltage.cpp:71:16: warning: unused variable 'l' [-Wunused-variable]
  int n,m,i,j,k,l,root=0,cnt1=0;
                ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5240 KB Output is correct
2 Correct 8 ms 5116 KB Output is correct
3 Correct 7 ms 5112 KB Output is correct
4 Correct 7 ms 5112 KB Output is correct
5 Incorrect 7 ms 5240 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 11364 KB Output is correct
2 Correct 89 ms 15332 KB Output is correct
3 Correct 72 ms 13356 KB Output is correct
4 Correct 146 ms 20284 KB Output is correct
5 Correct 16 ms 6388 KB Output is correct
6 Incorrect 90 ms 14308 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 11364 KB Output is correct
2 Correct 51 ms 16740 KB Output is correct
3 Correct 61 ms 16744 KB Output is correct
4 Correct 7 ms 5240 KB Output is correct
5 Correct 78 ms 16612 KB Output is correct
6 Correct 76 ms 12260 KB Output is correct
7 Incorrect 107 ms 15076 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 14684 KB Output is correct
2 Correct 112 ms 22432 KB Output is correct
3 Correct 9 ms 5880 KB Output is correct
4 Correct 138 ms 19396 KB Output is correct
5 Correct 102 ms 20580 KB Output is correct
6 Correct 117 ms 19232 KB Output is correct
7 Incorrect 158 ms 20188 KB Output isn't correct
8 Halted 0 ms 0 KB -