Submission #1027394

#	Time	Username	Problem	Language	Result	Execution time	Memory
1027394		BuzzyBeez	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	2 ms	12888 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
	
vector<pair<int, int>> adj[N + 8];
pair<int, int> E1[N + 8], E2[N + 8];

pair<int, int> fixed(int u, int v) {return {min(u, v), max(u, v)};}
map<pair<int, int>, int> F;

void add_edge(int u, int v, int id) {
	adj[u].push_back({v, id}); adj[v].push_back({u, id});
	++F[fixed(u, v)]; E1[id] = {u, v};
}

struct Disjoint_Set_Union {
	vector<int> par, sz;
	void init(int n) {
		par.assign(n + 8, 0); sz.assign(n + 8, 1);
		iota(par.begin(), par.end(), 0);
	}
	int find(int u) {return (par[u] == u ? u : (par[u] = find(par[u])));}
	bool join(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return 0;
		if (sz[u] < sz[v]) swap(u, v);
		par[v] = u; sz[u] += sz[v];
		return 1;
	}
} DSU;

int tin[N + 8], tout[N + 8], low[N + 8], d[N + 8];
pair<int, int> euler[N * 2 + 8];
pair<int, int> SpT[20][N * 2 + 8];
int dp[N + 8]; bool vis[N + 8];

void build_SpT(int n) {
	for (int lg = 0; (1 << lg) <= n; ++lg) for (int i = 1; i + (1 << lg) - 1 <= n; ++i) {
		if (!lg) SpT[lg][i] = euler[i];
		else SpT[lg][i] = min(SpT[lg - 1][i], SpT[lg - 1][i + (1 << (lg - 1))]);
	}
}

pair<int, int> rmq(int l, int r) {
	if (l > r) swap(l, r);
	int lg = __lg(r - l + 1);
	return min(SpT[lg][l], SpT[lg][r - (1 << lg) + 1]);
}

int LCA(int u, int v) {return rmq(tin[u], tin[v]).second;}

struct Solver {
	int timer; vector<tuple<int, int, int>> bridges;
	vector<pair<int, int>> Tadj[N + 8];
	Solver() {}
	
	void init(int n) {timer = 0; DSU.init(n);}
	
	void add_tree_edge(int u, int v, int id) {
		Tadj[u].push_back({v, id}); Tadj[v].push_back({u, id});
		// cout << u << ' ' << v << ' ' << id << '\n';
	}
	
	void DFS_build(int u, int p) {
		tin[u] = low[u] = ++timer;
		for (auto [v, id] : adj[u]) if (v != p) {
			if (tin[v]) low[u] = min(low[u], tin[v]);
			else {
				DFS_build(v, u); low[u] = min(low[u], low[v]);
				if (low[v] > tin[u] && F[fixed(u, v)] == 1) {
					bridges.push_back({u, v, id});
					// cout << u << " -> " << v << " is a bridge!!\n";
				}
				else DSU.join(u, v);
			}
		}
	}
	
	void DFS_EulerTour(int u, int p) {
		tin[u] = ++timer; euler[timer] = {d[u], u};
		for (auto [v, id] : Tadj[u]) if (v != p) {
			d[v] = d[u] + 1; DFS_EulerTour(v, u);
			euler[++timer] = {d[u], u};
		}
		tout[u] = timer;
	}
	
	void build_tree(int n) {
		for (int i = 1; i <= n; ++i) if (!tin[i]) DFS_build(i, i);
		for (auto [u, v, id] : bridges) add_tree_edge(DSU.find(u), DSU.find(v), id);
		timer = 0; 
		for (int i = 1; i <= n; ++i) if (!tout[i]) DFS_EulerTour(i, i);
		build_SpT(timer);
	}
	
	// u -> par[u] : -1; par[u] -> u: 1
	
	int A;
	void add_constraint(int u, int v) { // u --> v
		u = DSU.find(u); v = DSU.find(v);
		A = LCA(u, v);
		--dp[u]; ++dp[v]; 	
	}
	
	void DFS_sweep(int u, int p) {
		vis[u] = 1;
		for (auto [v, id] : Tadj[u]) if (v != p) DFS_sweep(v, u), dp[u] += dp[v];
		// cout << u << ' ' << dp[u] << '\n';
	}
	
	void DFS_label(int u, int p) {
		for (auto [v, id] : Tadj[u]) if (v != p) {
			DFS_label(v, u);
			if (!dp[v]) continue;
			else {
				E1[id].first = DSU.find(E1[id].first); 
				E1[id].second = DSU.find(E1[id].second);
				if (dp[v] < 0) E2[id] = {v, u};
				else E2[id] = {u, v}; 
			}
		}
	}
	
	void solve(int n) {
		for (int i = 1; i <= n; ++i) if (!vis[i]) DFS_sweep(i, i),  DFS_label(i, i);
	}
} DS;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, u, v; cin >> n >> m; DS.init(n);
	for (int i = 1; i <= m; ++i) cin >> u >> v, add_edge(u, v, i);
	DS.build_tree(n);
	int q; cin >> q;
	while (q--) cin >> u >> v, DS.add_constraint(u, v);
	DS.solve(n);
	// for (int i = 1; i <= m; ++i) cout << E1[i].first << ' ' << E1[i].second << ' ' << E2[i].first << ' ' << E2[i].second << '\n';
	for (int i = 1; i <= m; ++i)
		if (!E2[i].first) cout << 'B';
		else if (E1[i] == E2[i]) cout << 'L';
		else cout << 'R';
}

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