Submission #285996

#TimeUsernameProblemLanguageResultExecution timeMemory
285996BlagojceOne-Way Streets (CEOI17_oneway)C++11
100 / 100
438 ms30456 KiB
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

const ll inf = 1e18;
const ld eps = 1e-13;
const ll mod = 1e9+7; 
const int i_inf = 1e9;
const int mxn = 1e5;
mt19937 _rand(time(NULL));
clock_t timer = clock();

int n, m;
vector<pii> g[mxn];
int ans[mxn];
int dep[mxn];
bool vis[mxn];
bool bridge[mxn];


void dfs0(int u, int ed){
	vis[u] = true;
	int mindepth = dep[u];
	for(auto e : g[u]){
		if(e.nd == ed) continue;
		if(!vis[e.st]){
			dep[e.st] = dep[u] + 1;
			dfs0(e.st, e.nd);
		}
		mindepth = min(mindepth, dep[e.st]);
	}
	if(mindepth >= dep[u]){
		bridge[ed] = true;
	}
	else{
		dep[u] = mindepth;
	}
}

int group[mxn];
void dfs1(int u, int col){
	vis[u] = true;
	group[u] = col;
	for(auto e : g[u]){
		if(vis[e.st] || bridge[e.nd]) continue;
		dfs1(e.st, col);
	}
}
vector<pii> tree[mxn];

int sparse[mxn][20];
int depth[mxn];

void dfs2(int u, int p){
	vis[u] = true;
	sparse[u][0] = p;
	fr(i, 1, 20) sparse[u][i] = sparse[sparse[u][i-1]][i-1];
	for(auto e : tree[u]){
		if(e.st == p) continue;
		depth[e.st] = depth[u] + 1;
		dfs2(e.st, u);
	}
}
int lca(int a, int b){
	int d = min(depth[a], depth[b]);
	for(int i = 19; i >= 0; i --){
		if(depth[a] - (1<<i) >= d) a = sparse[a][i];
		if(depth[b] - (1<<i) >= d) b = sparse[b][i];
	}
	if(a == b) return a;
	for(int i = 19; i >= 0; i --){
		if(sparse[a][i] != sparse[b][i]){
			a = sparse[a][i];
			b = sparse[b][i];
		}
	}
	return sparse[a][0];
}
int val1[mxn];
int val2[mxn];

void dfs3(int u, int p, int ed){
	for(auto e : tree[u]){
		if(e.st == p) continue;
		dfs3(e.st, u, e.nd);
		val1[u] += val1[e.st];
		val2[u] += val2[e.st];
	}
	if(u == p) return;
	if(val1[u] > 0){
		if(ed > 0){
			ans[ed-1] = 2;
		}else{
			ans[-ed-1] = 1;
		}
	}
	if(val2[u] > 0){
		if(ed > 0){
			ans[ed-1] = 1;
		}
		else{
			ans[-ed-1] = 2;
		}
	}
}

void solve(){
	cin >> n >> m;
	int l[m], r[m];
	fr(i, 0, m){
		int u, v;
		cin >> u >> v;
		--u, --v;
		
		l[i] = u;
		r[i] = v;
		
		if(u == v){
			continue;
		}
		g[u].pb({v, i});
		g[v].pb({u, i});
	}
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs0(i, -1);
	}
	memset(vis, false, sizeof(vis));
	int col = 0;
	fr(i, 0, n){
		if(vis[i]) continue;
		dfs1(i, col);
		++col;
	}
	fr(i, 0, m){
		if(!bridge[i] || l[i] == r[i]) continue;

		int a = group[l[i]];
		int b = group[r[i]];
		
		tree[a].pb({b, i+1});
		tree[b].pb({a, -(i+1)});
	}
	memset(vis, false, sizeof(vis));
	vector<int> R;
	fr(i, 0, col){
		if(vis[i]) continue;
		dfs2(i, i);
		R.pb(i);
	}
	int p;
	cin >> p;
	bool answered[mxn];
	memset(answered, false, sizeof(answered));
	fr(i, 0, p){
		int u, v;
		cin >> u >> v;
		--u, --v;
		u = group[u];
		v = group[v];
		if(u == v) continue;
		
		int k = lca(u, v);
		
		
		val1[u] ++;
		val1[k] --;
		
		val2[v] ++;
		val2[k] --;
	}
	
	for(auto u : R){
		dfs3(u, u, 0);
	}
	
	fr(i, 0, m){
		if(ans[i] == 0) cout<<'B';
		else if(ans[i] == 1) cout<<'R';
		else cout<<'L';
	}
	cout<<endl;
	
}

int main(){
	solve();
}
	
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...