제출 #607513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
607513		UncoolAnon	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	9 ms	20948 KiB

oneway

#include <bits/stdc++.h> 
 
 
#define pii pair<int,int> 
#define F first 
#define S second 
#define mp make_pair 
 
using namespace std; 
const int N=100001,lg=19;  
int tim=0; 
int sp[lg][N]; 
vector<int> adj[N],tin(N),tout(N),low(N),vis(N); 
map<int,int> up[N],down[N]; 
map<pii,int> m,s; 
map<pii,int> cnt; 
bool SET(int a, int b){
	if(cnt[mp(a,b)]==1) s[mp(a,b)]=s[mp(b,a)]=1; 
	return 1; 
}
bool is_bridge(int a,int b){return s[mp(a,b)]; }
void dfs(int a, int p){
	vis[a]=1; 
	sp[0][a]=p; 
	for(int i=1;i<lg;i++)
		if(sp[i-1][a]!=-1)
			sp[i][a]=sp[i-1][sp[i-1][a]]; 
	tin[a]=++tim,low[a]=tim; 
	for(int&x:adj[a]){
			if(x==p) continue; 
			if(vis[x]) 
				low[a]=min(low[a],tin[x]); 
			else{
				dfs(x,a);
				low[a]=min(low[a],low[x]); 
				if(low[x]>tin[a]) SET(x,a); 
			}
	}
	tout[a]=++tim; 
	return ; 
}
int is_ancestor(int a, int b){
	return (tin[a]<=tin[b]&&tout[b]<=tout[a]); 
}
int lca(int a, int b){
	if(is_ancestor(a,b)) return a; 
	for(int i=lg-1;i>-1;--i)
		if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b))
			a=sp[i][a]; 
	return sp[0][a]; 
}
int blca(int a, int b){
	if(is_ancestor(a,b)) return -1;  
	for(int i=lg-1;i>-1;--i)
		if(sp[i][a]!=-1&&!is_ancestor(sp[i][a],b))
			a=sp[i][a]; 
	return a; 
}
void go(int a, int p,int dcnt,int ucnt){
	dcnt+=down[a][0]; 
	ucnt+=up[a][0]; 
	vis[a]=0; 
	//cout<<dcnt<<" "<<ucnt<<" "<<a<<endl; 
	for(int&x:adj[a]){
		if(vis[x]){
			dcnt+=down[a][x]; 
			ucnt+=up[a][x];
			if(dcnt&&ucnt){} 
			else if(dcnt||ucnt){
				if(dcnt){
					m[mp(a,x)]=1; 
					m[mp(x,a)]=-1; 
				} 
				else{
					m[mp(a,x)]=-1; 
					m[mp(x,a)]=1; 
				}
			}
			go(x,a,dcnt,ucnt); 
			dcnt-=down[a][x]; 
			ucnt-=up[a][x];
		}
	}
		dcnt+=down[a][0]; 
	ucnt+=up[a][0]; 
}
int main(){
	for(int i=0;i<lg;i++) for(int j=0;j<N;j++) sp[i][j]=-1; 
	int n,meme; 
	cin>>n>>meme;
	vector<pii> ed; 
	while(meme--){
		int a,b; 
		cin>>a>>b; 
		adj[a].push_back(b); 
		adj[b].push_back(a); 
		cnt[mp(a,b)]++; 
		cnt[mp(b,a)]++; 
		ed.push_back(mp(a,b)); 
	}
	for(int i=1;i<=n;i++)
		if(!vis[i])
			dfs(i,-1); 
	int q; 
	cin>>q; 
	vector<int> path; 
	function<bool(int,int)> launch=[&](int a, int b){
		vis[a]=0; 
		path.push_back(a); 
		if(a==b) return 1; 
		for(int&x:adj[a])
			if(vis[x]&&launch(x,b))
				return 1; 
		path.pop_back(); 
		return 0; 
	}; 
	while(q--){
		int a,b;
		cin>>a>>b; 
		/*for(int i=1;i<=n;i++) vis[i]=1; 
		path.clear(); 
		launch(a,b); 
		for(int i=0;i+1<path.size();i++){
			m[mp(path[i],path[i+1])]=1; 
			m[mp(path[i+1],path[i])]=-1; 
		}*/
		int lc=lca(a,b) ; 
		if(lc!=a){
			up[lc][blca(a,b)]++; 
			up[a][0]--;
		}
		if(lc!=b){
			down[lc][blca(b,a)]++;
			down[b][0]--; 
		}
	}
	for(int i=1;i<=n;i++)
		if(vis[i]) 
			go(i,-1,0,0);
	for(pii&x:ed){
		if(x.F!=x.S&&is_bridge(x.F,x.S)){
			if(m[x]==1)cout<<"R";  
			else if(m[x]==-1)cout<<"L"; 
			else cout<<"B"; 
		}
		else cout<<"B"; 
	}
	return 0; 	
}

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