제출 #1329630

#제출 시각아이디문제언어결과실행 시간메모리
1329630ppmn_6One-Way Streets (CEOI17_oneway)C++20
100 / 100
42 ms14532 KiB
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
 
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
    const time_point start_time;
public:
    Timer(): start_time(now()) {}
    rep elapsed_time() const {
		return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
	}
} timer;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, m, q;
	cin >> n >> m;
	vector<vector<array<int, 3>>> graph(n + 1);
	vector<int> depth(n + 1), low(n + 1, n), cnt(n + 1, 0);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		graph[u].push_back({v, i, 1});
		graph[v].push_back({u, i, 0});
	}
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		cnt[v]++; cnt[u]--;
	}
	vector<bool> vis(n + 1, 0);
	vector<char> ans(m, 0);
	auto dfs = [&] (auto self, int u, int e)->bool {
		vis[u] = 1;
		for (auto &[v, id, dir] : graph[u]) {
			if (id == e) {
				continue;
			}
			if (vis[v]) {
				ans[id] = 'B';
				low[u] = min({low[u], depth[u], depth[v]});
			}
			else {
				depth[v] = depth[u] + 1;
				if (self(self, v, id) || !cnt[v]) {
					ans[id] = 'B';
				}
				else {
					ans[id] = (cnt[v] > 0) ^ dir ? 'L' : 'R';
				}
				cnt[u] += cnt[v];
				low[u] = min(low[u], low[v]);
			}
		}
		return low[u] < depth[u];
	};
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			depth[i] = 0;
			dfs(dfs, i, -1);
		}
	}
	for (auto &x : ans) {
		cout << x;
	}
	
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...