Submission #305132

#	Time	Username	Problem	Language	Result	Execution time	Memory
305132		miss_robot	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	326 ms	40056 KiB

oneway

#include <bits/stdc++.h>

#pragma GCC optimize("O3")

using namespace std;

const int N = 1e5+1, L = 17;
int n, m, q, c;
int num[N], low[N], bridge[N], p[L][N], up[N], dir[N], in[N], out[N], height[N];
pair<int, int> e[N];
vector<int> g[N], ind[N];
vector<int> h[N], dni[N];
char sol[N];

void dfs(int u, int l){
	num[u] = low[u] = ++c;
	for(int i = 0, v, x; i < (int)g[u].size(); i++){
		v = g[u][i], x = ind[u][i];
		if(!num[v]){
			dfs(v, x);
			if(low[v] > num[u]) bridge[x] = 1;
			low[u] = min(low[u], low[v]);
		}
		if(x != l) low[u] = min(low[u], num[v]);
	}
}

void fnd(int u){
	if(num[u]) return;
	num[u] = c;
	for(int i = 0, v, x; i < (int)g[u].size(); i++){
		v = g[u][i], x = ind[u][i];
		if(bridge[x]) continue;
		fnd(v);
	}
}

void tree(int u, int l, int d){
	p[0][u] = l;
	height[u] = d++;
	for(int i = 0, v, x; i < (int)h[u].size(); i++){
		v = h[u][i], x = dni[u][i];
		if(v == l){
			up[u] = x;
			if(num[e[x].first] != u) dir[u] = 1;
		}
		else{
			tree(v, u, d);
		}
	}
}

int kth(int u, int k){
	for(int i = L-1; i >= 0; i--)
		if(k >= (1<<i))
			u = p[i][u], k -= (1<<i);
	return u;
}

int lca(int u, int v){
	if(height[u] < height[v]) swap(u, v);
	u = kth(u, height[u]-height[v]);
	if(u == v) return u;
	for(int i = L-1; i >= 0; i--)
		if(p[i][u] != p[i][v])
			u = p[i][u], v = p[i][v];
	return p[0][u];
}

void solve(int u){
	for(int v : h[u]){
		if(v != p[0][u]){
			solve(v);
			in[u] += in[v];
			out[u] += out[v];
		}
	}
	if(out[u]){
		if(dir[u]) sol[up[u]] = 'L';
		else sol[up[u]] = 'R';
	}
	if(in[u]){
		if(dir[u]) sol[up[u]] = 'R';
		else sol[up[u]] = 'L';
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for(int i = 0, u, v; i < m; i++){
		cin >> u >> v;
		u--, v--;
		e[i] = {u, v};
		g[u].push_back(v), g[v].push_back(u);
		ind[u].push_back(i), ind[v].push_back(i);
		sol[i] = 'B';
	}
	for(int i = 0; i < n; i++) if(!num[i]) dfs(i, -1);
	c = 0;
	for(int i = 0; i < n; i++) num[i] = 0;
	for(int i = 0; i < n; i++){
		if(num[i]) continue;
		c++;
		fnd(i);
	}
	for(int i = 0, u, v; i < m; i++){
		if(!bridge[i]) continue;
		tie(u, v) = e[i];
		h[num[u]].push_back(num[v]), h[num[v]].push_back(num[u]);
		dni[num[u]].push_back(i), dni[num[v]].push_back(i);
	}
	for(int i = 1; i <= c; i++) if(!p[0][i]) tree(i, i, 0);
	for(int j = 1; j < L; j++)
		for(int i = 1; i <= c; i++)
			p[j][i] = p[j-1][p[j-1][i]];
	cin >> q;
	for(int i = 0, u, v, a; i < q; i++){
		cin >> u >> v;
		u--, v--;
		u = num[u], v = num[v];
		a = lca(u, v);
		out[u]++, out[a]--;
		in[v]++, in[a]--;
	}
	for(int i = 1; i <= c; i++) if(!height[i]) solve(i);
	cout << sol << "\n";
}

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