oj.uz

Submission #572504

# Submission time Handle Problem Language Result Execution time Memory
572504 2022-06-04T14:22:47 Z _karan_gandhi One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 212 KB 
#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

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];

	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]--;
			}
		}
	}

	if (u != 0 && 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;
		edges.emplace_back(a - 1, b - 1);
		if (a == b) continue;
		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]++;
	}

	dfs(0, 0);

	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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -