Submission #135797

#	Time	Username	Problem	Language	Result	Execution time	Memory
135797		Adhyyan1252	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	223 ms	24296 KiB

oneway

#define NDEBUG
#include<bits/stdc++.h>
 
using namespace std;
 
struct edge{
	int u, v; 
};
 
int n, m; 
vector<vector<int> > g, in, out;
vector<vector<int> > newg;
vector<edge> e;
 
int next(int cur, int eid){
	assert(eid < e.size());
	return e[eid].u + e[eid].v - cur;
}
 
vector<int> vis1, evis;
 
void dfs(int cur){
	vis1[cur] = 1;
	for(int eid: g[cur]){
		if(evis[eid]) continue;
		evis[eid] = 1;
		int adj = next(cur, eid);
		out[cur].push_back(eid);
		in[adj].push_back(eid);
 
		if(!vis1[adj])	dfs(adj);
	}
}
 
 
//SCC code
 
vector<int> euler;
 
void dfs2(int cur){
	vis1[cur] = 1;
	for(int eid: out[cur]){
		int adj = next(cur, eid);
		if(vis1[adj] == 0) dfs2(adj);
	}
	euler.push_back(cur);
}
 
 
void dfs3(int cur, int comp){
	vis1[cur] = comp;
	for(int eid: in[cur]){
		int adj = next(cur, eid);
		if(vis1[adj] == -1) dfs3(adj, comp);
	}
}
 
vector<int> val;
vector<char> ans;
vector<int> vis2;
void dfs4(int cur, int parid){
	vis2[cur] = 1;
	for(int eid: newg[cur]){
		if(eid == parid) continue;
		int adj = vis1[e[eid].u] + vis1[e[eid].v] - cur;
		assert(adj != cur) ;
		if(!vis2[adj]) dfs4(adj, eid);
		val[cur] += val[adj];
	}
	if(parid != -1){
		if(val[cur] == 0) ans[parid] = 'B';
		else if((val[cur] > 0)^(vis1[e[parid].u] == cur)){
			ans[parid] = 'R';
		}else{
			ans[parid] = 'L';
		}
	}else{
		assert(val[cur] == 0);
	}
}
 
 
signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n>>m;
	g.resize(n);
	in.resize(n);
	out.resize(n);
	e.resize(m);
	ans.resize(m);
	for(int i = 0; i < m; i++){
		int u, v; cin>>u>>v; u--, v--;
		e[i] = {u, v};
		if(u == v) continue;
		g[u].push_back(i);
		g[v].push_back(i);
	}
 
	vis1 = vector<int>(n, 0);
	evis = vector<int>(m, 0);
	for(int i = 0; i < n; i++){
		if(!vis1[i]) dfs(i);
	}
	vis1 = vector<int>(n, 0);
	for(int i = 0; i < n; i++){
		if(!vis1[i]) dfs2(i);
	}
 
	reverse(euler.begin(), euler.end());
	vis1 = vector<int>(n, -1);
	int compCount = 0;
	for(int u: euler){
		if(vis1[u] == -1){
			dfs3(u, u);
			compCount++;
		}
	}
	
 
	// for(int i = 0; i < n; i++){
	// 	cout<<i<<" : "<<vis1[i]<<endl;
	// }
 
	in.clear(); out.clear();
	newg.resize(n);
 
	int edgeCount = 0;
	for(int i = 0; i < m; i++){
		int u = vis1[e[i].u], v = vis1[e[i].v];
		if(u == v){
			ans[i] = 'B';
			continue;
		}
		edgeCount++;
		newg[u].push_back(i);
		newg[v].push_back(i);
	}
	assert(compCount - 1 == edgeCount);
	//made tree
	int q; cin>>q;
	val.resize(n);
	for(int i = 0; i < q; i++){
		int x, y; cin>>x>>y; x--, y--;
		x = vis1[x], y= vis1[y];
		//if(x == y) continue;
		val[x] -= 1;
		val[y] += 1;
	}
	
	vis2 = vector<int>(n, 0);
	for(int i = 0; i < n; i++){
		if(vis2[i] == 0 && vis1[i] == i) dfs4(i, -1);
	}
 
	for(int i = 0; i < m; i++){
		if(ans[i] == 'B' || ans[i] == 'R' || ans[i] == 'L'){
			cout<<ans[i];
		}else{
			assert(false); 
		}
	}
	cout<<endl;
	return 0;
}

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