Submission #438622

#	Time	Username	Problem	Language	Result	Execution time	Memory
438622		huangqr	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	131 ms	16416 KiB

oneway

#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;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40