Submission #607520

#	Time	Username	Problem	Language	Result	Execution time	Memory
607520		UncoolAnon	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	755 ms	61352 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); 
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; 
}
pii go(int a, int p){
	vis[a]=0; 
	int upi=0,downi=0; 
	for(int&x:adj[a])
		if(vis[x]){
			pii da= go(x,a); 
			if(da.F) m[mp(x,a)]=1,m[mp(a,x)]=-1; 
			if(da.S) m[mp(x,a)]=-1,m[mp(a,x)]=1; 
			upi+=da.F; 
			downi+=da.S; 
		}
	upi+=up[a]; downi+=down[a]; 
	return mp(upi,downi); 
}
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; 
		int lc=lca(a,b) ; 
		up[lc]--,up[a]++; 
		down[lc]--,down[b]++; 
	}
	for(int i=1;i<=n;i++)
		if(vis[i]) 
			go(i,-1);
	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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40