oj.uz

Submission #761431

# Submission time Handle Problem Language Result Execution time Memory
761431 2023-06-19T15:53:14 Z siewjh One-Way Streets (CEOI17_oneway) C++17
100 / 100
 135 ms 31940 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN], btadj[MAXN];
pair<int, int> pedge[MAXN];
int tvis[MAXN], lo[MAXN], comp[MAXN], p[MAXN][20], dep[MAXN], treedir[MAXN];
bool isbridge[MAXN], vis[MAXN];
int preind = 0, cmpind = -1;
void dfs(int x, int peind){
	tvis[x] = lo[x] = preind++;
	for (auto nxt : adj[x]){
		int nn = nxt.first, ne = nxt.second;
		if (ne == peind) continue;
		if (tvis[nn] != -1) lo[x] = min(lo[x], tvis[nn]);
		else{
			dfs(nn, ne);
			lo[x] = min(lo[x], lo[nn]);
			if (lo[nn] > tvis[x]) isbridge[ne] = 1;
		}
	}
}
void dfs2(int x){
	vis[x] = 1; comp[x] = cmpind;
	for (auto nxt : adj[x]){
		int nn = nxt.first, ne = nxt.second;
		if (vis[nn]) continue;
		if (isbridge[ne]) continue;
		dfs2(nn);
	}
}
void dfs3(int x, int par, int depth){
	p[x][0] = par; dep[x] = depth;
	for (auto nxt : btadj[x]){
		int nn = nxt.first, ne = nxt.second;
		if (nn == par) continue;
		pedge[nn] = {x, ne};
		dfs3(nn, x, depth + 1);
	}
}
int lca(int a, int b){
	if (dep[b] > dep[a]) swap(a, b);
	for (int k = 19; k >= 0; k--)
		if (p[a][k] != -1 && dep[p[a][k]] >= dep[b])
			a = p[a][k];
	if (a == b) return a;
	for (int k = 19; k >= 0; k--)
		if (p[a][k] != p[b][k]) {
			a = p[a][k];
			b = p[b][k];
		}
	return p[a][0];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nodes, edges; cin >> nodes >> edges;
	vector<pair<int, int>> elist(edges);
	for (int i = 0; i < edges; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back({b, i});
		adj[b].push_back({a, i});
		elist[i] = {a, b};
	}
	memset(tvis, -1, sizeof(tvis));
	for (int i = 1; i <= nodes; i++)
		if (tvis[i] == -1)
			dfs(i, -1);
	for (int i = 1; i <= nodes; i++)
		if (!vis[i]){
			cmpind++;
			dfs2(i);
		}
	for (int i = 0; i <= edges; i++)
		if (isbridge[i]){
			int a = elist[i].first, b = elist[i].second;
			a = comp[a], b = comp[b];
			btadj[a].push_back({b, i});
			btadj[b].push_back({a, i});
		}
	memset(dep, -1, sizeof(dep));
	for (int i = 0; i <= cmpind; i++)
		if (dep[i] == -1)
			dfs3(i, -1, 0);
	for (int k = 1; k <= 19; k++)
		for (int i = 0; i <= cmpind; i++){
			if (p[i][k - 1] == -1) p[i][k] = -1;
			else p[i][k] = p[p[i][k - 1]][k - 1];
		}
	int queries; cin >> queries;
	vector<tuple<int, int, int, int>> vpath(queries);
	for (int i = 0; i < queries; i++){
		int a, b, lcav; cin >> a >> b;
		a = comp[a], b = comp[b];
		lcav = lca(a, b);
		vpath[i] = make_tuple(dep[lcav], a, b, lcav);
	}
	sort(vpath.begin(), vpath.end()); // noi q5 moment
	vector<char> ans(edges, 'B');
	for (int i = 0; i < queries; i++){
		int lcad, a, b, lcav; tie(lcad, a, b, lcav) = vpath[i];
		while (a != lcav){
			int pa = pedge[a].first, pe = pedge[a].second;
			if (ans[pe] != 'B') break;
			if (comp[elist[pe].first] == a) ans[pe] = 'R';
			else ans[pe] = 'L';
			a = pa;
		}
		while (b != lcav){
			int pb = pedge[b].first, pe = pedge[b].second;
			if (ans[pe] != 'B') break;
			if (comp[elist[pe].first] == b) ans[pe] = 'L';
			else ans[pe] = 'R';
			b = pb;
		}
	}
	for (int i = 0; i < edges; i++) cout << ans[i];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5928 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5796 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5928 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5796 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct
11 Correct 28 ms 11984 KB Output is correct
12 Correct 31 ms 12876 KB Output is correct
13 Correct 35 ms 14340 KB Output is correct
14 Correct 42 ms 17444 KB Output is correct
15 Correct 46 ms 18804 KB Output is correct
16 Correct 60 ms 24964 KB Output is correct
17 Correct 66 ms 26280 KB Output is correct
18 Correct 59 ms 24944 KB Output is correct
19 Correct 61 ms 27468 KB Output is correct
20 Correct 32 ms 12448 KB Output is correct
21 Correct 29 ms 12232 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5716 KB Output is correct
2 Correct 3 ms 5716 KB Output is correct
3 Correct 3 ms 5844 KB Output is correct
4 Correct 3 ms 5928 KB Output is correct
5 Correct 4 ms 5972 KB Output is correct
6 Correct 3 ms 5844 KB Output is correct
7 Correct 3 ms 5972 KB Output is correct
8 Correct 3 ms 5972 KB Output is correct
9 Correct 3 ms 5796 KB Output is correct
10 Correct 3 ms 5844 KB Output is correct
11 Correct 28 ms 11984 KB Output is correct
12 Correct 31 ms 12876 KB Output is correct
13 Correct 35 ms 14340 KB Output is correct
14 Correct 42 ms 17444 KB Output is correct
15 Correct 46 ms 18804 KB Output is correct
16 Correct 60 ms 24964 KB Output is correct
17 Correct 66 ms 26280 KB Output is correct
18 Correct 59 ms 24944 KB Output is correct
19 Correct 61 ms 27468 KB Output is correct
20 Correct 32 ms 12448 KB Output is correct
21 Correct 29 ms 12232 KB Output is correct
22 Correct 135 ms 29028 KB Output is correct
23 Correct 121 ms 27536 KB Output is correct
24 Correct 101 ms 27660 KB Output is correct
25 Correct 125 ms 31940 KB Output is correct
26 Correct 121 ms 28644 KB Output is correct
27 Correct 119 ms 27624 KB Output is correct
28 Correct 31 ms 11532 KB Output is correct
29 Correct 53 ms 14664 KB Output is correct
30 Correct 57 ms 14848 KB Output is correct
31 Correct 49 ms 15104 KB Output is correct
32 Correct 92 ms 20568 KB Output is correct