제출 #572511

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
572511		_karan_gandhi	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	70 ms	17460 KiB

oneway

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

#define all(v) v.begin(), v.end()
#define endl '\n'
#define pl(var) " [" << #var << ": " << (var) << "] "
#define ll long long

template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "[" << p.first << ", " << p.second << "]"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) { cout << "["; for(int i = 0; i < (int)v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) { cin >> p.first; return cin >> p.second; }

vector<vector<pair<int, int>>> adj;
vector<pair<int, int>> edges;
vector<bool> vis;
vector<int> dp, dep, start_below;
vector<int> start, en;
vector<pair<int, int>> back_edges; // alignment of the edges // 0 is don't flip
string ans;

void dfs(int u, int edgeID, int d = 0) {
	// cout << pl(u) << endl;
	if (vis[u]) return;
	vis[u] = 1;
	dep[u] = d;

	start_below[u] = start[u] - en[u];

	// cout << pl(u) << adj[u] << endl;

	for (auto [v, id] : adj[u]) {
		if (id == edgeID) continue;

		if (!vis[v]) {
			dfs(v, id, d + 1);

			start_below[u] += start_below[v];
			dp[u] += dp[v];
		} else {
			if (dep[u] > dep[v]) {
				// goes up
				dp[u]++;
			} else {
				dp[u]--;
			}
		}
	}

	// cout << pl(u) << pl(dp[u]) << endl;

	if (edgeID != -1 && dp[u] == 0) {
		// back edge
		if (start_below[u] != 0) {
			bool dir = start_below[u] > 0;
			// check what direction the edge was originally oriented
			if (edges[edgeID].first == u) {
				dir = !dir;
			}
			back_edges.emplace_back(edgeID, dir);
		}
	}
}

void solve() {
	int n, m; cin >> n >> m;

	adj.resize(n);
	// dfsTree.resize(n);
	vis.resize(n);
	start_below.resize(n);
	dp.resize(n);
	start.resize(n);
	en.resize(n);
	dep.resize(n);

	for (int i = 0; i < m; i++) {
		int a, b; cin >> a >> b;
		a--, b--;
		if (a == b) continue;
		edges.emplace_back(a, b);
		adj[a].emplace_back(b, i);
		adj[b].emplace_back(a, i);
	}

	int p; cin >> p;

	for (int i = 0; i < p; i++) {
		int a, b; cin >> a >> b;

		a--, b--;
		start[a]++;
		en[b]++;
	}

	for (int i = 0; i < n; i++) if (!vis[i]) dfs(i, -1, 0);

	// cout << pl(vis[1]) << endl;

	ans = string(m, 'B');

	for (auto [edge, dir] : back_edges) {
		ans[edge] = (!dir ? 'R' : 'L');
	}

	cout << ans << endl;
}

int main() {
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T = 1;
	// cin >> T;
	while (T--)
		solve();
}

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