Submission #639408

#TimeUsernameProblemLanguageResultExecution timeMemory
639408inksamuraiUsmjeri (COCI17_usmjeri)C++17
0 / 140
430 ms135556 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=300001,lon=19; int n,m; vi adj[_n]; map<pii,int> es; int spr[lon][_n*3],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); // } }

Compilation message (stderr)

usmjeri.cpp: In function 'int main()':
usmjeri.cpp:127:9: warning: unused variable 'ds' [-Wunused-variable]
  127 |     int ds=get_dist(s,up);
      |         ^~
usmjeri.cpp:129:9: warning: variable 'id' set but not used [-Wunused-but-set-variable]
  129 |     int id=s;
      |         ^~
usmjeri.cpp:131:9: warning: unused variable 'dt' [-Wunused-variable]
  131 |     int dt=get_dist(t,up);
      |         ^~
usmjeri.cpp:139:9: warning: unused variable 'dt' [-Wunused-variable]
  139 |     int dt=get_dist(t,up);
      |         ^~
#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...