Submission #954606

#	Time	Username	Problem	Language	Result	Execution time	Memory
954606		mocha	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	79 ms	41196 KiB

oneway

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mx = 2e5+5;

int n, m, q;
vector<int> g[mx];
int dfn[mx], low[mx];
int ans[mx];
int pe[mx];
int t;
bool vis[mx], vise[mx];
vector<int> ng[mx];
int a[mx];
int dep[mx];

struct Edge {
	int u, v;
	int id;
} e[mx];

void print(int a[], int n) {
	for (int i=1;i<=n;i++) {
		cout << a[i] << " ";
	}
	cout << "\n";
}

void pt() {
	print(dep, n);
	print(ans, m);
	print(a, n);
}

void dfs1(int x, int peg, int d) {
	low[x] = dfn[x] = ++t;
	pe[x] = peg;
	vis[x] = 1;
	dep[x] = d;
	for (int i:g[x]) {
		if (vise[i]) continue;
		vise[i] = 1;
		auto [u, v, id] = e[i];
		if (u != x) swap(u, v);
		if (!vis[v]) {
			ng[u].push_back(v);
			ng[v].push_back(u);
			dfs1(v, i, d+1);
			low[u] = min(low[u], low[v]);
		} else {
			low[u] = min(low[u], dfn[v]);
		}
	}	
	if (low[x] != dfn[x]) {
		ans[peg] = 3;
	}
}

void dfs2(int x, int p) {
	vis[x] = 1;
	for (int i:ng[x]) {
		if (i == p) continue;
		dfs2(i, x);
		a[x] += a[i];
	}
	if (ans[pe[x]] == 3) return;
	auto [u, v, id] = e[pe[x]];
	if (a[x] > 0) {
		if (dep[u] > dep[v]) {
			ans[id] = 1;
		} else {
			ans[id] = 2;
		}
	} else if (a[x] < 0) {
		if (dep[u] < dep[v]) {
			ans[id] = 1;
		} else {
			ans[id] = 2;
		}
	}
}

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

	cin >> n >> m;
	for (int i=1;i<=m;i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(i);
		g[v].push_back(i);
		e[i] = {u, v, i};
	}
	for (int i=1;i<=n;i++) {
		if (!vis[i]) {
			dfs1(i, 0, 1);
		}
	}
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		a[u]++;
		a[v]--;
	}
	for (int i=1;i<=n;i++) {
		vis[i] = 0;
	}
	for (int i=1;i<=n;i++) {
		if (!vis[i]) {
			dfs2(i, 0);
		}
	}
	for (int i=1;i<=m;i++) {
		if (ans[i] == 3 or ans[i] == 0) {
			cout << 'B';
		} else if (ans[i] == 1) {
			cout << 'R';
		} else {
			cout << 'L';
		}
	}
	cout << "\n";
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs1(long long int, long long int, long long int)':
oneway.cpp:43:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |   auto [u, v, id] = e[i];
      |        ^
oneway.cpp: In function 'void dfs2(long long int, long long int)':
oneway.cpp:67:7: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |  auto [u, v, id] = e[pe[x]];
      |       ^

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