Submission #438622

#TimeUsernameProblemLanguageResultExecution timeMemory
438622huangqrOne-Way Streets (CEOI17_oneway)C++14
100 / 100
131 ms16416 KiB
#include<bits/stdc++.h> using namespace std; typedef int ll; typedef pair<ll,ll> pl; const ll lim=1e5+5; ll n,m,q; vector<char>ans; struct UFDS{ ll par[lim]; UFDS(){ for(int i=0;i<lim;i++)par[i]=i; } ll findset(ll pos){ if(pos==par[pos])return pos; else return par[pos]=findset(par[pos]); } void mergeset(ll a,ll b){ a = findset(a),b = findset(b); if(a!=b)par[b]=a; } }ufds; struct Edge{ ll x,a,b,idx;//x is the other guy, a and b are original order of edge Edge(ll xx,ll aa,ll bb,ll ii){ x=xx,a=aa,b=bb,idx=ii; } Edge(){} }; struct Graph{ vector<Edge>adjl[lim],nontree; ll par[lim],depth[lim]; Edge paredge[lim]; bool vis[lim],root[lim]; Graph(){ fill(vis,vis+lim,0); fill(root,root+lim,0); fill(depth,depth+lim,0); par[1]=1; depth[1]=0; } void dfs(ll pos,ll pre_idx){ vis[pos]=1; for(Edge &E:adjl[pos]){ if(E.idx==pre_idx){ swap(E,adjl[pos].back()); adjl[pos].pop_back(); break; } } for(Edge E:adjl[pos]){ if(!vis[E.x]){ vis[E.x]=1; par[E.x]=pos; paredge[E.x]=E; depth[E.x]=depth[pos]+1; dfs(E.x,E.idx); } else if(pos<E.x){ //prevent duplication (each extra edge goes into nontree once only) nontree.push_back(E); } } return; } void proc(Edge E){//marks a cycle in the tree ll ha=ufds.findset(E.a),hb=ufds.findset(E.b); while(ha!=hb){ if(depth[ha]<depth[hb])swap(ha,hb); ufds.mergeset(par[ha],ha); ha=ufds.findset(par[ha]); } } void init(){//Part 1, init graph and process the nontree edges for(int i=1;i<=n;i++){ if(vis[i]==0)dfs(i,-1),root[i]=1; } for(auto E:nontree)proc(E);//mark the cycles } //Part 2, answering the queries void query(ll a,ll b){ ll ha=ufds.findset(a),hb=ufds.findset(b); while(ha!=hb){ if(depth[ha]>depth[hb]){ ll nxt=ufds.findset(par[ha]); ufds.mergeset(nxt,ha); Edge E=paredge[ha]; assert((E.a==ha)^(E.b==ha)); ans[E.idx]= (E.a==ha)?'R':'L'; ha=nxt; } else{ ll nxt=ufds.findset(par[hb]); ufds.mergeset(nxt,hb); Edge E=paredge[hb]; assert((E.a==hb)^(E.b==hb)); ans[E.idx]= (E.a==hb)?'L':'R'; hb=nxt; } } } }; int main(){ ios_base::sync_with_stdio(0),cin.tie(NULL); cin>>n>>m; ans=vector<char>(m,'B');//Assume all edges can bidirectional at first Graph G; for(int i=0;i<m;i++){ ll a,b; cin>>a>>b; if(a==b)continue; G.adjl[a].push_back(Edge(b,a,b,i)); G.adjl[b].push_back(Edge(a,a,b,i)); } G.init(); cin>>q; while(q--){ ll a,b; cin>>a>>b; G.query(a,b); } for(char c:ans)cout<<c; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...