Submission #246942

#	Time	Username	Problem	Language	Result	Execution time	Memory
246942		oolimry	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	126 ms	14348 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);
		}
	}
}

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 = 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){
			if(depth[s] >= depth[t]){
				if(!pathCompressed[s]) label[s] = labelS;
				pathCompressed[s] = true;
				nodes.push_back(s);
				s = p[s];
			}
			else{
				if(!pathCompressed[t]) label[t] = labelT;
				pathCompressed[t] = true;
				nodes.push_back(t);
				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;
		
		int a = edges[e].first;
		int b = edges[e].second;
		
		bool swapped = false;
		
		if(depth[a] > depth[b]){
			swap(a, b);
			swapped = true;
		}
				
		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]];
	}
	
	return 0;
}

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