Submission #938386

#	Time	Username	Problem	Language	Result	Execution time	Memory
938386		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3055 ms	65660 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define fr first
#define sc second
const long long INF=1e17,N=2e5+6;
vector<int> ar[N],up(N),tin(N),color(N);
vector<bool> used(N);
int timer,mxcol=0;
map<pair<int,int>,bool> mp;
map<pair<int,int>,int> e_cnt;
void bridge(int x, int p=-1){
	used[x]=1;
	tin[x]=up[x]=timer++;
	for(auto it: ar[x]){
		if(it==p) continue;
		if(used[it])
			up[x]=min(up[x],tin[it]);
		else{
			bridge(it,x);
			up[x]=min(up[x],up[it]);
			if(up[it]>tin[x]){
				mp[{it,x}]=1;
				mp[{x,it}]=1;
			}
		}
	}
}
void dfs(int x, int c){
	color[x]=c;
	used[x]=1;
	for(auto it: ar[x]){
		if(!used[it] && (!mp[{x,it}] || e_cnt[{x,it}]!=1))
			dfs(it,c);
	}
}

int n,m;
int ans[N],A[N],B[N];
map<pair<int,int>,int> edge;
vector<pair<int,int>> g[N];
int k;
int vis[N];
int DFS(int x, int f){
	if(x==f) return 1;
	vis[x]=1;
	bool res=0;
	for(auto it: g[x]){
		if(vis[it.fr]) continue;
		if(DFS(it.fr,f)){
			int t=it.sc;
			if(t<0)
				ans[-t]=0;
			else
				ans[t]=1;
			res=1;
		}
	}
	vis[x]=0;
	return res;
}
int c=0;
void get(){
	cin>>k;
	for(int i=0;i<k;i++){
		int a,b;cin>>a>>b;a--,b--;
		DFS(color[a],color[b]);
	}
	for(int i=1;i<=m;i++){
		if(ans[i]==2) cout<<'B';
		else if(ans[i]==1) cout<<'R';
		else cout<<'L';
	}
}
void solve(){
	cin>>n>>m;
	vector<pair<int,int>> e;
	for(int i=0;i<m;i++){
		ans[i+1]=2;
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		e_cnt[{a,b}]++;
		e_cnt[{b,a}]++;
		ar[a].pb(b);
		ar[b].pb(a);
		edge[{a,b}]=i+1;
		edge[{b,a}]=-i-1;
		e.pb({a,b});
	}
	for(int i=0;i<n;i++){
		if(!used[i])
			bridge(i);
	}
	used.assign(N,0);
	
	for(int i=0;i<n;i++){
		if(!used[i])
			dfs(i,++c);
	}	
	for(auto it: e){
		if(color[it.fr]!=color[it.sc]){
			g[color[it.fr]].pb({color[it.sc],edge[it]});
			g[color[it.sc]].pb({color[it.fr],edge[{it.sc,it.fr}]});
		}
	}
	get();
}
main(){
	int T=1;
	//cin>>T;
	while(T--){
		solve();
	}
}

Compilation message (stderr)

oneway.cpp:111:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  111 | main(){
      | ^~~~

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