Submission #677900

#TimeUsernameProblemLanguageResultExecution timeMemory
677900Ahmed57Usmjeri (COCI17_usmjeri)C++14
14 / 140
244 ms48680 KiB
#include <bits/stdc++.h> using namespace std; //DSU int mn1 = 100001; int pr1[100001],pr2[100001]; int gs1[100001],gs2[100001]; int findleader1(int x){ if(pr1[x]==x){ return x; } return pr1[x] = findleader1(pr1[x]); } bool samegroup1(int x,int y){ int led1 = findleader1(x); int led2 = findleader1(y); return led1==led2; } void mergegroup1(int x,int y){ int led1 = findleader1(x); int led2 = findleader1(y); if(led1==led2)return; if(gs1[led1]>gs1[led2]){ pr1[led2]=led1; gs1[led1]+=gs1[led2]; }else{ pr1[led1]=led2; gs1[led2]+=gs1[led1]; } } int findleader2(int x){ if(pr2[x]==x){ return x; } return pr2[x] = findleader2(pr2[x]); } bool samegroup2(int x,int y){ int led1 = findleader2(x); int led2 = findleader2(y); return led1==led2; } void mergegroup2(int x,int y){ int led1 = findleader2(x); int led2 = findleader2(y); if(led1==led2)return; if(gs2[led1]>gs2[led2]){ pr2[led2]=led1; gs2[led1]+=gs2[led2]; }else{ pr2[led1]=led2; gs2[led2]+=gs2[led1]; } } int dep[100001]; int P[100001][20]; int ed[100001]; int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int k=17;k>=0;k--) { if(dep[x]-(1<<k) >= dep[y]) x=P[x][k]; } if(x==y) return x; for(int k=17;k>=0;k--) { if(P[x][k] != P[y][k]) x=P[x][k],y=P[y][k]; } return P[x][0]; } vector<pair<int,int>> adj[100001]; void dfs(int i,int pr,int e){ P[i][0] = pr; ed[i] = e; dep[i] = dep[pr]+1; for(int j = 1;j<20;j++){ P[i][j] = P[P[i][j-1]][j-1]; } for(auto j:adj[i]){ if(j.first!=pr){ dfs(j.first,i,j.second); } } } vector<int> e[100001]; int vis[100001] , col[100001]; bool ss = 1; void color(int i,int c){ vis[i] = 1;col[i] = c; for(auto j:e[i]){ if(vis[j]==0){ color(j,!c); }else{ if(col[j]==c){ ss = 0; } } } } int main(){ //freopen("poklonin6.txt","r",stdin); for(int i = 0;i<mn1;i++){ pr1[i] = i , pr2[i] = i , gs1[i] = 1, gs2[i] = 1; } int n,m; cin>>n>>m; for(int i = 0;i<n-1;i++){ int a,b;cin>>a>>b; adj[a].push_back({b,i}); adj[b].push_back({a,i}); } dfs(1,0,0); while(m--){ int a,b;cin>>a>>b; int lc = lca(a,b); int cur = a , last = -1; if(dep[a]>dep[lc]){ last = ed[a]; } while(dep[cur]>dep[lc]){ for(int j = 19;j>=0;j--){ if(samegroup1(cur,P[cur][j])){ cur = P[cur][j]; } } if(dep[cur]>dep[lc]){ mergegroup1(cur,P[cur][0]); mergegroup2(last,ed[cur]); } cur = P[cur][0]; if(dep[cur]>dep[lc]){ mergegroup2(last,ed[cur]); } } int last2 = last; swap(a,b); cur = a , last = -1; if(dep[a]>dep[lc]){ last = ed[a]; } while(dep[cur]>dep[lc]){ for(int j = 19;j>=0;j--){ if(samegroup1(cur,P[cur][j])){ cur = P[cur][j]; } } if(dep[cur]>dep[lc]){ mergegroup1(cur,P[cur][0]); mergegroup2(last,ed[cur]); } cur = P[cur][0]; if(dep[cur]>dep[lc]){ mergegroup2(last,ed[cur]); } } if(last!=-1&&last2!=-1){ e[findleader2(last)].push_back(findleader2(last2)); e[findleader2(last2)].push_back(findleader2(last)); } } long long ans = 1; for(int i = 0;i<n-1;i++){ if(!vis[findleader2(i)]){ color(findleader2(i),0); ans*=2;ans%=(1000000007); } } if(!ss){ cout<<"0\n"; }else cout<<ans; }
#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...