oj.uz

Submission #246938

# Submission time Handle Problem Language Result Execution time Memory
246938 2020-07-10T15:31:16 Z oolimry One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 14900 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;

ii edges[100005];
int p[100005];
int label[100005];
int edgeId[100005];

vector<ii> adj[100005];
bool isBridge[100005];
int low[100005];
int depth[100005];
bool pathCompressed[100005];

void tarjan(int u){
	low[u] = depth[u];
	for(ii e : adj[u]){
		int v = e.first, id = e.second;
		if(depth[v] == 0){
			p[v] = u;
			depth[v] = depth[u] + 1;
			tarjan(v);
			if(low[v] > depth[u]) isBridge[id] = true;
			low[u] = min(low[u], low[v]);
			edgeId[v] = id;
		}
		else if(v != p[u]) low[u] = min(low[u], depth[v]);
	}
}

int component[100005];
int cnt = 1;
void compress(int s){
	component[s] = cnt;
	for(ii e : adj[s]){
		int v = e.first, id = e.second;
		if(component[v] == 0 && !isBridge[id]){
			compress(v);
		}
	}
}

vector<ii> tree[100005];
int ans[100005];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n, m;
	cin >> n >> m;
	
	for(int i = 1;i <= m;i++){
		int a, b; cin >> a >> b;
		edges[i] = ii(a, b);
		adj[a].push_back(ii(b,i));
		adj[b].push_back(ii(a,i));
	}
	
	for(int i = 1;i <= n;i++){
		if(depth[i] != 0) continue;
		depth[i] = 1;
		tarjan(i);
	}
	
	
	for(int i = 1;i <= n;i++){
		if(component[i] != 0) continue;
		compress(i);
		cnt++;
	}
	
	/*
	for(int i = 1;i <= m;i++){
		if(isBridge[i]){
			int a = component[edges[i].first];
			int b = component[edges[i].second];
			tree[a].push_back(ii(b,i));
			tree[b].push_back(ii(a,i));
		}
	}
	*/
	
	for(int i = 1;i <= m;i++){
		if(isBridge[i]){
			int a = edges[i].first, b = edges[i].second;
			if(component[a] == component[b]) isBridge[i] = false;
		}
	}
	
	
	int Q; cin >> Q;	
	while(Q--){
		int s, t; cin >> s >> t;
		int labelS = 1, labelT = 2;
		vector<int> nodes;
		while(s != t){
			//cout << s << " " << t << endl;
			if(depth[s] >= depth[t]){
				//cout << s << " " << labelS << endl;
				if(!pathCompressed[s]) label[s] = labelS;
				pathCompressed[s] = true;
				s = p[s];
			}
			else{
				//cout << t << " " << labelT << endl;
				if(!pathCompressed[t]) label[t] = labelT;
				pathCompressed[t] = true;
				t = p[t];
			}
		}
		
		int P = s;
		for(int x : nodes){
			p[x] = P;
		}
	}
	
	for(int i = 1;i <= n;i++){
		int e = edgeId[i];
		if(e == 0) continue;
		if(!isBridge[e]) continue;
		
		int a = edges[e].first;
		int b = edges[e].second;
		
		bool swapped = false;
		
		if(depth[a] > depth[b]){
			swap(a, b);
			swapped = true;
		}
		
		//cout << a << " " << b << " " << depth[a] << " " << depth[b] << " " << label[b] << "\n";
		
		int ANS = label[b];
		if(ANS == 0) continue;
		if(swapped) ANS = 3 - ANS;
		ans[e] = ANS;
	}
	
	string S = "BLR";
	for(int i = 1;i <= m;i++){
		if(!isBridge[i]) ans[i] = 0;
		cout << S[ans[i]];
		//if(ans[i] != 0){
		//	cout << ans[i] << " " << edges[i].first << " " << edges[i].second << "\n";
		//}
	}
	
	
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 51 ms 10744 KB Output is correct
12 Correct 60 ms 11768 KB Output is correct
13 Correct 69 ms 12920 KB Output is correct
14 Correct 87 ms 13892 KB Output is correct
15 Correct 98 ms 14072 KB Output is correct
16 Correct 65 ms 12280 KB Output is correct
17 Correct 86 ms 14072 KB Output is correct
18 Correct 97 ms 12792 KB Output is correct
19 Correct 84 ms 14900 KB Output is correct
20 Correct 62 ms 11640 KB Output is correct
21 Correct 59 ms 11512 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 7 ms 5120 KB Output is correct
3 Correct 8 ms 5248 KB Output is correct
4 Correct 8 ms 5248 KB Output is correct
5 Correct 8 ms 5120 KB Output is correct
6 Correct 8 ms 5120 KB Output is correct
7 Correct 8 ms 5248 KB Output is correct
8 Correct 8 ms 5248 KB Output is correct
9 Correct 8 ms 5120 KB Output is correct
10 Correct 8 ms 5120 KB Output is correct
11 Correct 51 ms 10744 KB Output is correct
12 Correct 60 ms 11768 KB Output is correct
13 Correct 69 ms 12920 KB Output is correct
14 Correct 87 ms 13892 KB Output is correct
15 Correct 98 ms 14072 KB Output is correct
16 Correct 65 ms 12280 KB Output is correct
17 Correct 86 ms 14072 KB Output is correct
18 Correct 97 ms 12792 KB Output is correct
19 Correct 84 ms 14900 KB Output is correct
20 Correct 62 ms 11640 KB Output is correct
21 Correct 59 ms 11512 KB Output is correct
22 Execution timed out 3078 ms 13560 KB Time limit exceeded
23 Halted 0 ms 0 KB -