Submission #135709

#	Time	Username	Problem	Language	Result	Execution time	Memory
135709		Adhyyan1252	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	2 ms	504 KiB

oneway

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct edge{
	int u, v; 
};
int n, m; 
vector<vector<int> > g, in, out;
vector<set<int> > newg;
vector<edge> e;

int next(int cur, int eid){
	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]) 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;
void dfs4(int cur, int parid){
	for(int eid: newg[cur]){
		if(eid == parid) continue;
		int adj = vis1[e[eid].u] + vis1[e[eid].v] - cur;
		assert(adj != cur) ;
		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);
	dfs(0);

	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].insert(i);
		newg[v].insert(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;
	}
	assert(vis1[0] == 0);
	dfs4(0, -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;
}

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