Submission #45093

#	Time	Username	Problem	Language	Result	Execution time	Memory
45093		qoo2p5	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	309 ms	53444 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

const int N = (int) 1e5 + 123;

struct E {
	int a, b;
};

int n, m;
E e[N];
vector<pair<int, int>> g[N];
bool vis[N];

int tmr;
int tin[N], fup[N];
bool is_bridge[N];

void dfs(int v, int from_id = -1) {
	tin[v] = tmr++;
	fup[v] = tin[v];
	vis[v] = 1;
	for (auto &it : g[v]) {
		if (it.second == from_id) {
			continue;
		}
		int u = it.first;
		if (vis[u]) {
			mini(fup[v], tin[u]);
		} else {
			dfs(u, it.second);
			mini(fup[v], fup[u]);
		}
	}
	
	for (auto &it : g[v]) {
		if (it.second == from_id) {
			continue;
		}
		int u = it.first;
		int id = it.second;
		if (fup[u] > tin[v]) {
			is_bridge[id] = 1;
		}
	}
}

int comps;
int which[N];
vector<pair<int, int>> adj[N];
char ans[N];

void find_comps(int v) {
	vis[v] = 1;
	which[v] = comps;
	for (auto &it : g[v]) {
		int u = it.first;
		int id = it.second;
		if (is_bridge[id]) {
			continue;
		}
		ans[id] = 'B';
		if (vis[u]) {
			continue;
		}
		find_comps(u);
	}
}

const int L = 20;
int up[N][L];
int depth[N];

void calc_lca(int v, int f = -1) {
	if (f == -1) {
		rep(i, 0, L) up[v][i] = v;
	} else {
		up[v][0] = f;
		rep(i, 1, L) up[v][i] = up[up[v][i - 1]][i - 1];
	}
	vis[v] = 1;
	for (auto &it : adj[v]) {
		int u = it.first;
		if (!vis[u]) {
			depth[u] = depth[v] + 1;
			calc_lca(u, v);
		}
	}
}

bool test(int mask, int bit) {
	return mask & (1 << bit);
}

int go(int v, int h) {
	rep(i, 0, L) if (test(h, i)) v = up[v][i];
	return v;
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	u = go(u, depth[u] - depth[v]);
	if (u == v) return u;
	per(i, L - 1, 0) {
		int uu = up[u][i];
		int vv = up[v][i];
		if (uu != vv) {
			u = uu, v = vv;
		}
	}
	return up[u][0];
}

int cnt_up[N], cnt_down[N];

void solve(int v, int fid = -1) {
	vis[v] = 1;
	for (auto &it : adj[v]) {
		int u = it.first;
		if (vis[u]) continue;
		solve(u, it.second);
		maxi(cnt_up[v], cnt_up[u] - 1);
		maxi(cnt_down[v], cnt_down[u] - 1);
	}
	
	assert(cnt_up[v] == 0 || cnt_down[v] == 0);
	if (fid != -1) {
		if (cnt_up[v] > 0) {
			if (which[e[fid].a] == v) {
				ans[fid] = 'R';
			} else {
				ans[fid] = 'L';
			}
		} else if (cnt_down[v] > 0) {
			if (which[e[fid].a] == v) {
				ans[fid] = 'L';
			} else {
				ans[fid] = 'R';
			}
		} else {
			ans[fid] = 'B';
		}
	}
}

void run() {
	cin >> n >> m;
	rep(i, 0, m) {
		cin >> e[i].a >> e[i].b;
		g[e[i].a].pb({e[i].b, i});
		g[e[i].b].pb({e[i].a, i});
	}
	
	rep(i, 1, n + 1) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	memset(vis, 0, sizeof vis);
	rep(i, 1, n + 1) {
		if (!vis[i]) {
			find_comps(i);
			comps++;
		}
	}
	memset(vis, 0, sizeof vis);
	rep(i, 0, m) {
		int u = which[e[i].a];
		int v = which[e[i].b];
		if (u != v) {
			adj[u].pb({v, i});
			adj[v].pb({u, i});
		}
	}
	rep(i, 0, comps) {
		if (!vis[i]) {
			calc_lca(i);
		}
	}
	memset(vis, 0, sizeof vis);
	
	int p;
	cin >> p;
	while (p--) {
		int x, y;
		cin >> x >> y;
		x = which[x], y = which[y];
		if (x == y) {
			continue;
		}
		
		int w = lca(x, y);
		maxi(cnt_up[x], depth[x] - depth[w]);
		maxi(cnt_down[y], depth[y] - depth[w]);
	}
	
	rep(i, 0, comps) {
		if (!vis[i]) {
			solve(i);
		}
	}
	
	rep(i, 0, m) {
		cout << ans[i];
	}
	cout << "\n";
}

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