Submission #639399

#TimeUsernameProblemLanguageResultExecution timeMemory
639399inksamuraiUsmjeri (COCI17_usmjeri)C++17
70 / 140
469 ms262144 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define per(i,n) for(int i=n-1;i>=0;i--) #define rng(i,c,n) for(int i=c;i<n;i++) #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define vec(...) vector<__VA_ARGS__> #define _3xaMC2q ios::sync_with_stdio(0),cin.tie(0) typedef long long ll; using pii=pair<int,int>; using vi=vector<int>; void print(){cout<<'\n';} template<class h,class...t> void print(const h&v,const t&...u){cout<<v<<' ',print(u...);} //e #define vp vec(pii) const int _n=500011,lon=19; int n,m; vi adj[_n]; map<pii,int> es; int spr[lon][_n],prs[lon][_n]; int par[_n],dpth[_n],tin[_n]; int _tm; vi tour; void dfs(int v){ tin[v]=_tm++; tour.pb(v); for(auto u:adj[v]){ if(u==par[v]) continue; dpth[u]=dpth[v]+1; par[u]=v; dfs(u); tour.pb(v); _tm++; } } int chmin(int v,int u){ return dpth[v]<dpth[u]?v:u; } void _gap_lca(){ dfs(0); rep(i,n){ prs[0][i]=par[i]; } rng(j,1,lon){ rep(i,n){ int up=prs[j-1][i]; prs[j][i]=up==-1?up:prs[j-1][up]; } } const int si_to=sz(tour); rep(i,si_to){ spr[0][i]=tour[i]; if(i+1<si_to){ spr[0][i]=chmin(spr[0][i],tour[i+1]); } } rng(j,1,lon){ rep(i,si_to){ int up=spr[j-1][i]; if(i+(1<<(j-1))<si_to){ up=chmin(up,spr[j-1][i+(1<<(j-1))]); } spr[j][i]=up; } } } int get_ancestor(int u,int v){ int i=tin[u],j=tin[v]; if(i==j) return v; if(i>j)swap(i,j),swap(u,v); int k=31-__builtin_clz(j-i); u=spr[k][i]; v=spr[k][j-(1<<k)]; return chmin(u,v); } int get_dist(int u,int v){ int up=get_ancestor(u,v); return dpth[v]+dpth[u]-2*dpth[up]; } int push_up(int s,int d){ per(i,lon){ if(d>>i&1){ s=prs[i][s]; } } return s; } signed main(){ _3xaMC2q; cin>>n>>m; rep(i,n-1){ int u,v; cin>>u>>v; u-=1,v-=1; es[minmax(u,v)]=i; adj[u].pb(v); adj[v].pb(u); } _gap_lca(); vi rbe(n,-1); //denotes edge from (i,pari) vec(vp) g(n-1); //denotes graph of edges in inital graph rep(i,m){ int s,t; cin>>s>>t; s-=1,t-=1; if(dpth[s]>dpth[t])swap(s,t); if(s!=t){ int up=get_ancestor(s,t); if(up!=s){ int ds=get_dist(s,up); int ns=push_up(s,ds-1); int id=s; rbe[id]=rbe[id]==-1?ns:chmin(rbe[id],ns); int dt=get_dist(t,up); int nt=push_up(t,dt-1); id=t; rbe[id]=rbe[id]==-1?nt:chmin(rbe[id],nt); int u=es[minmax(ns,up)],v=es[minmax(nt,up)]; g[u].pb(pii(1,v)); g[v].pb(pii(1,u)); }else{ int dt=get_dist(t,up); int nt=push_up(t,dt-1); int id=t; rbe[id]=rbe[id]==-1?nt:chmin(rbe[id],nt); } } } //add additional edges from rbe vi rbts; rep(i,n)rbts.pb(i); sort(rbts.begin(),rbts.end(),[&](int l,int r){return dpth[l]>dpth[r];}); for(auto s:rbts){ if(rbe[s]!=-1){ if(dpth[rbe[s]]<dpth[s]){ int up=rbe[s]; rbe[par[s]]=rbe[par[s]]==-1?up:chmin(rbe[par[s]],up); int u=es[minmax(s,par[s])],v=es[minmax(par[s],par[par[s]])]; g[u].pb(pii(0,v)); g[v].pb(pii(0,u)); } } } bool valid=1; vi usd(n-1,-1); auto rfs=[&](auto self,int v)->void{ for(auto e:g[v]){ int u=e.se; int w=e.fi; if(usd[u]==-1){ usd[u]=usd[v]^w; self(self,u); }else if(usd[u]!=(usd[v]^w)){ valid=0; } } }; ll ans=1; const ll mod=1000000007; rep(i,n-1){ if(usd[i]==-1){ usd[i]=0; ans=ans*2%mod; ans%=mod; rfs(rfs,i); } } if(!valid){ print(0); }else{ print(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...