Submission #246935

#	Time	Username	Problem	Language	Result	Execution time	Memory
246935		oolimry	One-Way Streets (CEOI17_oneway)	C++14	60 / 100	3032 ms	15864 KiB

oneway

#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;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:114:11: warning: unused variable 'x' [-Wunused-variable]
   for(int x : nodes){
           ^
oneway.cpp:113:7: warning: unused variable 'P' [-Wunused-variable]
   int P = s;
       ^

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40