Submission #547644

#	Time	Username	Problem	Language	Result	Execution time	Memory
547644		Mazaalai	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	117 ms	28972 KiB

oneway

#include <bits/stdc++.h>
#define pb push_back
#define LINE "----------------------------\n"
using namespace std;
using PII = pair <int, int>;
using VI = vector <int>;
const int N = 1e5 + 5;
int n, m, q;
vector <PII> paths[N];
vector <VI> edges;
string answ = ".LRB";
int par[N], dp[N], dp1[N], ans[N];
int find(int a) {
	if (par[a] == a) return a;
	return par[a] = find(par[a]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	par[b] = a;
}
bool vis[N], vis1[N];
int dfs(int pos, int p, int par = 0) {
	vis[pos] = 1;
	vis1[p] = 1;
	vector <int> curChildren;
	for (auto&[a, b] : paths[pos]) {
		if (vis1[b]) continue;
		if (vis[a]) {
			dp[pos]++;
			dp[a]--;
			vis1[b] = 1;
			continue;
		}
		curChildren.pb(a);
		dp[pos] += dfs(a, b, pos);
	}
	if (dp[pos] > 0) merge(pos, par);

	for (auto&a : curChildren) {
		dp1[pos] += dp1[a];
	}
	for (auto&[a, b] : paths[pos]) 
		if (find(a) == find(pos)) ans[b] |= 3;
	
	if (p > 0) {
		VI curEdge = {pos, par, p};
		// cout << LINE;
		// cout << "curEdge: " << pos << ' ' << par << ' ' << p << '\n';
		// cout << "edge: " << edges[p][0] << ' ' << edges[p][1] << ' ' << edges[p][2] << '\n';
		// cout << dp1[pos] << ' ' << ans[p] << '\n';
		if (dp1[pos] == 0) ans[p] |= 3;
		ans[p] |= ((curEdge == edges[p]) == (dp1[pos] > 0) ? 2 : 1);
	}
	return dp[pos];
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> m;
	edges.pb({0, 0, 0});
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b;
		edges.pb({a, b, i});
		paths[a].pb({b, i});
		paths[b].pb({a, i});
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int a, b;
		cin >> a >> b;
		dp1[a]++;
		dp1[b]--;
	}
	iota(par+1, par+1+n, 1);
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) dfs(i, 0);
	}
	// dfs(1, 0);
	// cout << LINE;
	// for (int i = 1; i <= n; i++) cout << i << ": " << find(i) << '\n';
	for (int i = 1; i <= m; i++) cout << answ[ans[i]]; cout << '\n';
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:85:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   85 |  for (int i = 1; i <= m; i++) cout << answ[ans[i]]; cout << '\n';
      |  ^~~
oneway.cpp:85:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |  for (int i = 1; i <= m; i++) cout << answ[ans[i]]; cout << '\n';
      |                                                     ^~~~

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