Submission #823661

#	Time	Username	Problem	Language	Result	Execution time	Memory
823661		NK_	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	72 ms	14728 KiB

oneway

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())

template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;

struct DSU {
	vi e; void init(int N) { e = vi(N, -1); }
	int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); }
	bool unite(int x, int y) {
		x = get(x), y = get(y); if (x == y) return 0;
		e[x] += e[y]; e[y] = x; return 1;
	}
};
int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	DSU D; D.init(N);
	V<V<pi>> adj(N); V<pi> ex, E;
	string ans(M, 'B');
	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;
		E.pb(mp(u, v));
		if (D.unite(u, v)) adj[u].pb(mp(v, i)), adj[v].pb(mp(u, i));
		else ex.pb(mp(u, v));
	}

	V<pi> par(N); vi dep(N, -1);
	function<void(int)> dfs = [&](int u) {
		for(auto& v : adj[u]) if (v.f != par[u].f) { 
			par[v.f] = mp(u, v.s); dep[v.f] = dep[u] + 1; dfs(v.f); 
		}
	};
	
	for(int r = 0; r < N; r++) if (dep[r] == -1) {
		par[r] = mp(-1, -1); dep[r] = 0; dfs(r);
	}


	D.init(N);
	for(const auto& p : ex) {
		int u, v; tie(u, v) = p;

		while(1) {
			int a = D.get(u), b = D.get(v);
			if (a == b) break;
			if (dep[a] < dep[b]) swap(a, b);
			assert(par[a].f != -1); D.unite(par[a].f, a);
		}
	}

	vi to(M, -1);
	int Q; cin >> Q;
	for(int i = 0; i < Q; i++) {
		int u, v; cin >> u >> v; --u, --v;
		if (D.get(u) == D.get(v)) continue;

		while(1) {
			int a = D.get(u), b = D.get(v);
			if (a == b) break;
			if (dep[a] < dep[b]) swap(a, b);
			to[par[a].s] = (D.get(u) == a ? par[a].f : a);
			assert(par[a].f != -1); D.unite(par[a].f, a);
		}
	}

	for(int i = 0; i < M; i++) if (to[i] != -1) {
		ans[i] = (E[i].f == to[i] ? 'L' : 'R');
	}

	cout << ans << nl;

    return 0;
}			

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