Submission #438577

#	Time	Username	Problem	Language	Result	Execution time	Memory
438577		huangqr	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	27 ms	16716 KiB

oneway

#include<bits/stdc++.h>
using namespace std;
typedef long long 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;
		//cout<<"pos:"<<pos<<"\n";
		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)
		//		cout<<"pos eidx:"<<pos<<" "<<E.idx<<"\n";
				nontree.push_back(E);
			}
		}
		return;
	}
	void roottrees(){
		for(int i=1;i<=n;i++){
			if(vis[i]==0)dfs(i,-1),root[i]=1;
		}
	}
	
	//Part 1, processing the nontree edges
	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);
			ans[paredge[ha].idx]='B';
			ha=ufds.findset(par[ha]);
		}
		return;
	}
	void genH(){
		for(auto E:nontree){
			ans[E.idx]='B';
			proc(E);
		}
		return;
		for(int i=1;i<=n;i++){
			if(root[i]){
	//			cout<<i<<" is a root\n";
				continue;
			}
			if(ufds.findset(i)==i){
		//		cout<<i<<" is a head\n";
	//			H->adjl[ufds.findset(par[i])].push_back(paredge[i]);
//				cout<<ufds.findset(par[i])<<" "<<(i)<<"\n";
//				cout<<"Edge:"<<paredge[i].a<<" "<<paredge[i].b<<"\n\n";
			}
		}
		return;
	}
	
	//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==ha)^(E.b==ha));
				ans[E.idx]= (E.a==hb)?'L':'R';
				hb=nxt;
			}
		}
		return;
	}
};

int main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL);
	cin>>n>>m;
	ans=vector<char>(m,'B');
	Graph G;
	for(int i=0;i<m;i++){
		ll a,b;
		cin>>a>>b;
		if(a==b){
			ans[i]='B';
			continue;
		}
		G.adjl[a].push_back(Edge(b,a,b,i));
		G.adjl[b].push_back(Edge(a,a,b,i));
	}
	G.roottrees();
	G.genH();
	cin>>q;
	while(q--){
		ll a,b;
		cin>>a>>b;
		G.query(a,b);
	}
//	for(auto x:G.nontree){
//		cout<<x.a<<" "<<x.b<<" "<<x.idx<<"\n";
//	}
	for(auto c:ans)cout<<c;
}

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