oj.uz

Submission #135797

# Submission time Handle Problem Language Result Execution time Memory
135797 2019-07-24T11:22:34 Z Adhyyan1252 One-Way Streets (CEOI17_oneway) C++11
100 / 100
 223 ms 24296 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 384 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 80 ms 8532 KB Output is correct
12 Correct 88 ms 10608 KB Output is correct
13 Correct 146 ms 13860 KB Output is correct
14 Correct 181 ms 17976 KB Output is correct
15 Correct 167 ms 19116 KB Output is correct
16 Correct 184 ms 19944 KB Output is correct
17 Correct 178 ms 21320 KB Output is correct
18 Correct 178 ms 19788 KB Output is correct
19 Correct 185 ms 22536 KB Output is correct
20 Correct 111 ms 12996 KB Output is correct
21 Correct 101 ms 12900 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 3 ms 632 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 3 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 80 ms 8532 KB Output is correct
12 Correct 88 ms 10608 KB Output is correct
13 Correct 146 ms 13860 KB Output is correct
14 Correct 181 ms 17976 KB Output is correct
15 Correct 167 ms 19116 KB Output is correct
16 Correct 184 ms 19944 KB Output is correct
17 Correct 178 ms 21320 KB Output is correct
18 Correct 178 ms 19788 KB Output is correct
19 Correct 185 ms 22536 KB Output is correct
20 Correct 111 ms 12996 KB Output is correct
21 Correct 101 ms 12900 KB Output is correct
22 Correct 214 ms 21380 KB Output is correct
23 Correct 209 ms 19728 KB Output is correct
24 Correct 219 ms 20044 KB Output is correct
25 Correct 223 ms 24296 KB Output is correct
26 Correct 203 ms 21068 KB Output is correct
27 Correct 202 ms 19896 KB Output is correct
28 Correct 46 ms 4344 KB Output is correct
29 Correct 125 ms 12560 KB Output is correct
30 Correct 129 ms 12596 KB Output is correct
31 Correct 133 ms 13236 KB Output is correct
32 Correct 152 ms 16636 KB Output is correct