제출 #230123

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
230123		islingr	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	115 ms	37344 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] + r[e] - u;
		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) continue;
				ans[e] = l[e] == u ? 'L' : 'R';
				if (s[v] < 0) ans[e] = 'L' + 'R' - ans[e];
			}
			s[u] += s[v];
		}
	}
}

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

	cin >> n >> m;
	rep(i, 0, m) {
		cin >> l[i] >> r[i]; --l[i]; --r[i];
		g[l[i]].eb(i); g[r[i]].eb(i);
		ans[i] = '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