oj.uz

Submission #135781

# Submission time Handle Problem Language Result Execution time Memory
135781 2019-07-24T11:07:27 Z Adhyyan1252 One-Way Streets (CEOI17_oneway) C++11
100 / 100
 308 ms 25992 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 = 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

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 504 KB Output is correct
4 Correct 15 ms 508 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 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 376 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 504 KB Output is correct
4 Correct 15 ms 508 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 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 376 KB Output is correct
11 Correct 78 ms 8916 KB Output is correct
12 Correct 99 ms 11200 KB Output is correct
13 Correct 122 ms 14260 KB Output is correct
14 Correct 163 ms 18464 KB Output is correct
15 Correct 172 ms 19660 KB Output is correct
16 Correct 187 ms 20328 KB Output is correct
17 Correct 180 ms 21864 KB Output is correct
18 Correct 187 ms 20308 KB Output is correct
19 Correct 175 ms 22992 KB Output is correct
20 Correct 136 ms 13400 KB Output is correct
21 Correct 98 ms 13108 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 504 KB Output is correct
4 Correct 15 ms 508 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 3 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 376 KB Output is correct
11 Correct 78 ms 8916 KB Output is correct
12 Correct 99 ms 11200 KB Output is correct
13 Correct 122 ms 14260 KB Output is correct
14 Correct 163 ms 18464 KB Output is correct
15 Correct 172 ms 19660 KB Output is correct
16 Correct 187 ms 20328 KB Output is correct
17 Correct 180 ms 21864 KB Output is correct
18 Correct 187 ms 20308 KB Output is correct
19 Correct 175 ms 22992 KB Output is correct
20 Correct 136 ms 13400 KB Output is correct
21 Correct 98 ms 13108 KB Output is correct
22 Correct 284 ms 23024 KB Output is correct
23 Correct 241 ms 21452 KB Output is correct
24 Correct 308 ms 21480 KB Output is correct
25 Correct 204 ms 25992 KB Output is correct
26 Correct 200 ms 22604 KB Output is correct
27 Correct 199 ms 21480 KB Output is correct
28 Correct 48 ms 4344 KB Output is correct
29 Correct 131 ms 14044 KB Output is correct
30 Correct 125 ms 14192 KB Output is correct
31 Correct 129 ms 14420 KB Output is correct
32 Correct 187 ms 18176 KB Output is correct