제출 #167901

#제출 시각아이디문제언어결과실행 시간메모리
167901rzbtUsmjeri (COCI17_usmjeri)C++14
28 / 140
719 ms96164 KiB
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define F first #define S second #define all(x) x.begin(),x.end() #define MAXN 300005 typedef long long ll; using namespace std; int n,m; vector<pair<int,int> > graf[MAXN]; vector<int> los[MAXN],dobar[MAXN]; int cale[MAXN][22]; int gcale[MAXN]; int dub[MAXN]; int sab[MAXN]; bool boja[MAXN],obidjen[MAXN]; const int MOD = 1e9+7; void init(int t,int o,int g,int h){ if(o){ cale[t][0]=o; gcale[t]=g; } dub[t]=h; for(auto x:graf[t]) if(x.F!=o) init(x.F,t,x.S,h+1); } int lca(int a,int b){ if(dub[a]<dub[b])swap(a,b); for(int j=21;j>=0;j--) if(dub[cale[a][j]]>=dub[b])a=cale[a][j]; if(a==b)return a; for(int j=21;j>=0;j--){ if(cale[a][j]!=cale[b][j]){ a=cale[a][j]; b=cale[b][j]; } } return cale[a][0]; } int predak(int a,int h){ for(int j=21;j>=0;j--) if(dub[cale[a][j]]>=h)a=cale[a][j]; return a; } void moguce(int t,bool tb){ //printf(" %d %d\n",t,tb); obidjen[t]=true; boja[t]=tb; for(auto x:los[t]){ if(obidjen[x] && tb == boja[x]){ printf("0"); exit(0); } if(!obidjen[x]) moguce(x,!tb); } } int konstruisi(int t,int o){ int z=sab[t]; for(auto x:graf[t]){ if(x.F==o)continue; int lol=konstruisi(x.F,t); if(lol && o){ dobar[x.S].pb(gcale[t]); dobar[gcale[t]].pb(x.S); } z+=lol; } return z; } void dfs(int t){ obidjen[t]=true; for(auto x:dobar[t]) if(!obidjen[x]) dfs(x); } int main() { scanf("%d %d", &n, &m); for(int i=1;i<n;i++){ int t1,t2; scanf("%d %d", &t1, &t2); graf[t1].pb(mp(t2,i)); graf[t2].pb(mp(t1,i)); } init(1,0,0,0); for(int j=1;j<22;j++) for(int i=1;i<=n;i++) cale[i][j]=cale[cale[i][j-1]][j-1]; dub[0]=-1; for(int i=1;i<=m;i++){ int t1,t2; scanf("%d %d", &t1, &t2); //printf(" %d\n",lca(t1,t2)); if(dub[t1]<dub[t2])swap(t1,t2); int l=lca(t1,t2); if(t2!=l){ int g1=gcale[predak(t1,dub[l]+1)]; int g2=gcale[predak(t2,dub[l]+1)]; los[g1].pb(g2); los[g2].pb(g1); } sab[t1]++; sab[predak(t1,dub[l]+1)]--; if(t2!=l){ sab[t2]++; sab[predak(t2,dub[l]+1)]--; } } for(int i=1;i<n;i++){ if(!obidjen[i]){ moguce(i,false); //printf("lol %d\n",i); } } memset(obidjen,0,sizeof(obidjen)); konstruisi(1,0); int bk=0; for(int i=1;i<n;i++){ if(!obidjen[i]){ dfs(i); bk++; //printf("lol %d\n",i); } } int res=1; for(int i=1;i<=bk;i++)res=(res+res)%(MOD); printf("%d",res); return 0; }

컴파일 시 표준 에러 (stderr) 메시지

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:93:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
usmjeri.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
usmjeri.cpp:107:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &t1, &t2);
         ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...