Submission #943389

#	Time	Username	Problem	Language	Result	Execution time	Memory
943389		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	509 ms	61896 KiB

oneway

#include <bits/stdc++.h>
#define ll long long
#define str string
#define ins insert
#define ld long double
#define pb push_back
#define pf push_front
#define pof pop_front()
#define pob pop_back()
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define sz size()
#define vll vector<ll>
#define bc back()
#define arr array
#define pll vector<pair<ll,ll>>
using namespace std;/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>*/
template<class S,class T>
bool chmin(S &a,const T &b) {
	return a>b?(a=b)==b:false;
}
template<class S,class T>
bool chmax(S &a,const T &b) {
	return a<b?(a=b)==b:false;
}
//void fre(string s){freopen((s+".in").c_str(),"r",stdin);freopen((s+".out").c_str(),"w",stdout);}
void start(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const ll inf=1e18;
const ll mod=998244353;
const ll N=1e5+5;
const ld eps=1e-9;
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];
void DFS(int x, int p){
	vis[x]=1;
	for(auto it: g[x]){
		if(it.fr==p) continue;
		DFS(it.fr,x);
		A[x]+=A[it.fr];
		B[x]+=B[it.fr];
	}
	for(auto it: g[x]){
		if(it.fr==p) continue;
		if(A[it.fr]!=B[it.fr]){
			int t=it.sc;
			if(t<0)
				ans[-t]=1;
			else
				ans[t]=0;
			if(B[it.fr]>A[it.fr]) ans[abs(t)]^=1;
		}
	}
}
int c=0;
void get(){
	cin>>k;
	for(int i=0;i<k;i++){
		int a,b;cin>>a>>b;a--,b--;
		A[color[a]]++,B[color[b]]++;
		//DFS(color[a],color[b]);
	}
	for(int i=1;i<=c;i++)
		if(!vis[i])
			DFS(i,-1);
	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();
}

signed main(){
	start();
    ll t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}
/*

9 11
1 2
2 1
1 3
3 4
4 5
3 5
4 6
2 7
2 8
8 9
7 1
2
7 5
9 6



*/

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