oj.uz

Submission #954606

# Submission time Handle Problem Language Result Execution time Memory
954606 2024-03-28T08:11:48 Z mocha One-Way Streets (CEOI17_oneway) C++14
100 / 100
 79 ms 41196 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19804 KB Output is correct
2 Correct 4 ms 20048 KB Output is correct
3 Correct 5 ms 20060 KB Output is correct
4 Correct 5 ms 20052 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 5 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20140 KB Output is correct
10 Correct 4 ms 20056 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19804 KB Output is correct
2 Correct 4 ms 20048 KB Output is correct
3 Correct 5 ms 20060 KB Output is correct
4 Correct 5 ms 20052 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 5 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20140 KB Output is correct
10 Correct 4 ms 20056 KB Output is correct
11 Correct 38 ms 30292 KB Output is correct
12 Correct 41 ms 31828 KB Output is correct
13 Correct 52 ms 33816 KB Output is correct
14 Correct 65 ms 34896 KB Output is correct
15 Correct 68 ms 35004 KB Output is correct
16 Correct 72 ms 33016 KB Output is correct
17 Correct 60 ms 35420 KB Output is correct
18 Correct 68 ms 32884 KB Output is correct
19 Correct 65 ms 37056 KB Output is correct
20 Correct 43 ms 32092 KB Output is correct
21 Correct 50 ms 31608 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 19804 KB Output is correct
2 Correct 4 ms 20048 KB Output is correct
3 Correct 5 ms 20060 KB Output is correct
4 Correct 5 ms 20052 KB Output is correct
5 Correct 4 ms 20060 KB Output is correct
6 Correct 4 ms 20060 KB Output is correct
7 Correct 5 ms 20060 KB Output is correct
8 Correct 4 ms 20060 KB Output is correct
9 Correct 4 ms 20140 KB Output is correct
10 Correct 4 ms 20056 KB Output is correct
11 Correct 38 ms 30292 KB Output is correct
12 Correct 41 ms 31828 KB Output is correct
13 Correct 52 ms 33816 KB Output is correct
14 Correct 65 ms 34896 KB Output is correct
15 Correct 68 ms 35004 KB Output is correct
16 Correct 72 ms 33016 KB Output is correct
17 Correct 60 ms 35420 KB Output is correct
18 Correct 68 ms 32884 KB Output is correct
19 Correct 65 ms 37056 KB Output is correct
20 Correct 43 ms 32092 KB Output is correct
21 Correct 50 ms 31608 KB Output is correct
22 Correct 76 ms 36440 KB Output is correct
23 Correct 79 ms 34060 KB Output is correct
24 Correct 77 ms 34132 KB Output is correct
25 Correct 76 ms 41196 KB Output is correct
26 Correct 72 ms 35820 KB Output is correct
27 Correct 74 ms 34092 KB Output is correct
28 Correct 26 ms 27472 KB Output is correct
29 Correct 64 ms 32588 KB Output is correct
30 Correct 54 ms 32592 KB Output is correct
31 Correct 60 ms 33108 KB Output is correct
32 Correct 60 ms 36300 KB Output is correct