Submission #696972

#	Time	Username	Problem	Language	Result	Execution time	Memory
696972		xuliu	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	4948 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define debug if(0)

const int N = 1e5 + 10;
vector<pair<int, int>> V[N], W[N];
vector<int> comp;
int low[N], no[N], de[N], val[N], c[N], T = 0, X = 0;
bool vis[N], bridge[N];

void dfs(int v, int eid=0) {
	vis[v] = 1;
	no[v] = T++;
	low[v] = no[v];
	for(auto e : V[v]) {
		int u = e.first, id = e.second;
		if(id == eid) continue;
		if(!vis[u]) {
			dfs(u, id);
			low[v] = min(low[v], low[u]);
		}
		else low[v] = min(low[v], no[u]);
		if(low[u] > no[v]) bridge[id] = 1;
	}
}

void dfs2(int v) {
	vis[v] = 1;
	c[v] = X;
	for(auto e : V[v]) {
		int u = e.first, id = e.second;
		if(bridge[id]) continue;
		if(!vis[u]) dfs2(u);
	}
}

void dfs3(int v) {
	vis[v] = 1;
	for(auto e : W[v]) {
		int u = e.first, id = e.second;
		if(!vis[u]) {
			if(val[u] > val[v]) de[id] = 1;
			else if(val[u] < val[v]) de[id] = 2;
			dfs3(u);
		}
	}
}

void clear(int n) {
	for(int i=0; i<=n; i++) vis[i] = 0;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, m, p; cin>>n>>m;
	for(int i=0; i<m; i++) {
		int a, b; cin>>a>>b;
		V[a].push_back({b, i});
		V[b].push_back({a, i});
	}
	for(int i=1; i<=n; i++) {
		if(!vis[i]) dfs(i);
	}
	clear(n);
	for(int i=1; i<=n; i++) {
		if(!vis[i]) {
			X++;
			dfs2(i);
		}
	}
	for(int i=1; i<=n; i++) {
		for(auto e : V[i]) {
			int u = e.first, id = e.second;
			if(c[i] != c[u]) W[c[i]].push_back({c[u], id});
		}
	}
	clear(n);
	cin>>p;
	for(int i=0; i<p; i++) {
		int a, b; cin>>a>>b;
		if(c[a] == c[b]) continue;
		val[c[a]]--;
		val[c[b]]++;
	}
	for(int i=1; i<=n; i++) {
		if(!vis[i]) dfs3(i);
	}
	for(int i=0; i<m; i++) {
		if(de[i] == 1) cout<<"R";
		else if(de[i] == 2) cout<<"L";
		else cout<<"B";
	}
}

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