oj.uz

Submission #135784

# Submission time Handle Problem Language Result Execution time Memory
135784 2019-07-24T11:10:25 Z Adhyyan1252 One-Way Streets (CEOI17_oneway) C++11
100 / 100
 268 ms 23836 KB 
#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 = 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);
	}
	//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

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.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 3 ms 508 KB Output is correct
4 Correct 4 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 760 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 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 3 ms 508 KB Output is correct
4 Correct 4 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 760 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 82 ms 7972 KB Output is correct
12 Correct 100 ms 10028 KB Output is correct
13 Correct 129 ms 13184 KB Output is correct
14 Correct 164 ms 17340 KB Output is correct
15 Correct 167 ms 18584 KB Output is correct
16 Correct 179 ms 19312 KB Output is correct
17 Correct 176 ms 20816 KB Output is correct
18 Correct 189 ms 19304 KB Output is correct
19 Correct 175 ms 21992 KB Output is correct
20 Correct 113 ms 12468 KB Output is correct
21 Correct 101 ms 12040 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 3 ms 508 KB Output is correct
4 Correct 4 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 760 KB Output is correct
8 Correct 4 ms 504 KB Output is correct
9 Correct 3 ms 504 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 82 ms 7972 KB Output is correct
12 Correct 100 ms 10028 KB Output is correct
13 Correct 129 ms 13184 KB Output is correct
14 Correct 164 ms 17340 KB Output is correct
15 Correct 167 ms 18584 KB Output is correct
16 Correct 179 ms 19312 KB Output is correct
17 Correct 176 ms 20816 KB Output is correct
18 Correct 189 ms 19304 KB Output is correct
19 Correct 175 ms 21992 KB Output is correct
20 Correct 113 ms 12468 KB Output is correct
21 Correct 101 ms 12040 KB Output is correct
22 Correct 205 ms 20764 KB Output is correct
23 Correct 213 ms 19208 KB Output is correct
24 Correct 216 ms 19304 KB Output is correct
25 Correct 214 ms 23836 KB Output is correct
26 Correct 268 ms 20456 KB Output is correct
27 Correct 219 ms 19304 KB Output is correct
28 Correct 51 ms 3704 KB Output is correct
29 Correct 155 ms 12020 KB Output is correct
30 Correct 120 ms 12084 KB Output is correct
31 Correct 137 ms 12468 KB Output is correct
32 Correct 144 ms 16292 KB Output is correct