oj.uz

Submission #246509

# Submission time Handle Problem Language Result Execution time Memory
246509 2020-07-09T13:29:45 Z oolimry One-Way Streets (CEOI17_oneway) C++14
0 / 100
 6 ms 2688 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];
void tarjan(int u){
	low[u] = depth[u];
	for(ii e : adj[u]){
		int v = e.first, id = e.second;
		if(depth[v] == 0){
			depth[v] = depth[u] + 1;
			tarjan(v);
			low[u] = min(low[u], low[v]);
			if(low[v] > depth[u]) isBridge[id] = true;
			p[v] = u;
			edgeId[v] = id;
		}
		else if(depth[v] < depth[u] - 1) low[u] = min(low[u], depth[v]);
	}
}

int component[100005];
int cnt = 1;
void compress(int s){
	queue<int> bfs; bfs.push(s);
	while(!bfs.empty()){
		int u = bfs.front(); bfs.pop();
		if(component[u] != 0) continue;
		component[u] = cnt;
		for(ii e : adj[u]){
			int v = e.first, id = e.second;
			if(isBridge[id]) continue;
			bfs.push(v);
		}
	}
	cnt++;
}

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);
	}
	
	for(int i = 1;i <= m;i++){
		if(isBridge[i]){
			int a = component[edge[i].first];
			int b = component[edge[i].second];
			tree[a].push_back(b);
			tree[b].push_back(a);
		}
	}
	*/
	
	int Q; cin >> Q;	
	while(Q--){
		int s, t; cin >> s >> t;
		int labelS = 1, labelT = 2;
		vector<int> nodes;
		while(s != t){
			if(depth[s] >= depth[t]){
				//cout << s << " " << labelS << "\n";
				label[s] = labelS;
				s = p[s];
			}
			else{
				//cout << t << " " << labelT << "\n";
				label[t] = labelT;
				t = p[t];
			}
		}
		
		int P = s;
		for(int x : nodes){
			p[x] = P;
		}
	}
	
	for(int i = 2;i <= n;i++){
		int e = edgeId[i];
		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(swapped) ANS = 3 - ANS;
		ans[e] = ANS;
	}
	
	string S = "BLR";
	for(int i = 1;i <= m;i++){
		cout << S[ans[i]];
	}
	
	return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Incorrect 6 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Incorrect 6 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2688 KB Output is correct
2 Incorrect 6 ms 2688 KB Output isn't correct
3 Halted 0 ms 0 KB -