Submission #230288

#	Time	Username	Problem	Language	Result	Execution time	Memory
230288		islingr	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	100 ms	37368 KiB

oneway

#include <iostream>
#include <vector>
using namespace std;

#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define trav(x, v) for (auto &x : v)

#define eb(x...) emplace_back(x)

template<class T> bool ckmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

constexpr int N = 1 << 20, M = 1 << 20;
int n, m;
vector<int> g[N];
char ans[M];
int tin[N], low[N], l[M], r[M], s[N], timer;

void dfs(int u, int p = -1) {
	low[u] = tin[u] = ++timer;
	trav(e, g[u]) {
		if (e == p) continue;
		int v = l[e] == u ? r[e] : l[e];
		if (tin[v]) ckmin(low[u], tin[v]);
		else {
			dfs(v, e);
			ckmin(low[u], low[v]);
			if (tin[u] < low[v]) {
				if (s[v] > 0) ans[e] = l[e] == u ? 'L' : 'R';
				if (s[v] < 0) ans[e] = l[e] == v ? 'L' : 'R';
			}
			s[u] += s[v];
		}
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	rep(e, 0, m) {
		cin >> l[e] >> r[e]; --l[e]; --r[e];
		g[l[e]].eb(e); g[r[e]].eb(e);
		ans[e] = 'B';
	}
	int q; cin >> q;
	while (q--) {
		int u, v; cin >> u >> v; --u; --v;
		++s[u]; --s[v];
	}
	rep(u, 0, n) if (!tin[u]) dfs(u);
	cout << ans;
}

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