Submission #135781

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

oneway

#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++){
		e[i].u = vis1[e[i].u];
		e[i].v = vis1[e[i].v];
		int u = e[i].u, v = e[i].v;
		if(u == v){
			ans[i] = 'B';
			continue;
		}
		edgeCount++;
		newg[u].push_back(i);
		newg[v].push_back(i);
	}
	//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 < n; i++){
		if(vis1[i] == i) assert(vis2[i]);
	}
	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;
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from oneway.cpp:1:
oneway.cpp: In function 'int next(int, int)':
oneway.cpp:15:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(eid < e.size());
         ~~~~^~~~~~~~~~

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