Submission #156084

#TimeUsernameProblemLanguageResultExecution timeMemory
156084HungAnhGoldIBO2020전압 (JOI14_voltage)C++14
0 / 100
149 ms20160 KiB
#include<iostream> #include<vector> #include<algorithm> #define int long long 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; 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,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=1;i<lis.size();i++){ if(i>0&&lis[i].first==lis[i-1].first&&lis[i].second==lis[i-1].second){ cnt1++; if(i==1){ cnt1++; } else{ if(lis[i-1].first!=lis[i-2].first||lis[i-1].second!=lis[i-2].second){ cnt1++; } } } } 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){ // cout<<"cac"<<endl; cout<<m-cnt1; 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 (stderr)

voltage.cpp: In function 'bool dfs(long long int, bool)':
voltage.cpp:13:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
voltage.cpp:12: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:33:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
voltage.cpp:32:18: warning: unused variable 'first1' [-Wunused-variable]
  bool first=true,first1=true;
                  ^~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=1;i<lis.size();i++){
          ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...