oj.uz

Submission #853600

# Submission time Handle Problem Language Result Execution time Memory
853600 2023-09-24T17:38:25 Z mbfibat One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 83108 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int N = 1e5 + 11;

int n, m;
char ans[N];
vector<int> adj[N];
map<ii, int> dir, org, cnt;

int height[N], lca[N][21];

int top = 0;
int cur[N], low[N];
map<ii, bool> is_bridge;

void dfs(int u, int p = 0) {
	cur[u] = low[u] = ++top;
	for (int v : adj[u]) {
		if (!cur[v]) {
			dfs(v, u);

			low[u] = min(low[u], low[v]);
//			cerr << u << ' ' << v << ' ' << low[v] << ' ' << cur[u] << '\n';
			if (low[v] > cur[u]) {
				is_bridge[ii(u, v)] = is_bridge[ii(v, u)] = (cnt[ii(u, v)] == 1);
				cerr << u << ' ' << v << ' ' << is_bridge[ii(u, v)] << '\n';				
			}
		} else if (v != p)
			low[u] = min(low[u], cur[v]);
	}
}

int id[N];
ii upd[N];
iii par[N];   
vector<iii> adj_compress[N];
void compress(int u) {
	id[u] = top;
//	cerr << u << ' ' << id[u] << '\n';
	for (int v : adj[u]) {
		if (id[v]) {
			if (id[v] != top) {
				adj_compress[id[u]].emplace_back(id[v], u, v);
				adj_compress[id[v]].emplace_back(id[u], v, u);
			}	
			continue;
		}
		if (is_bridge[ii(u, v)]) continue;

		compress(v);
	}
}

void dfs2(int u, int p = -1) {
	cur[u] = true;
	for (int j = 1; j <= 20; j++)
		lca[u][j] = lca[lca[u][j - 1]][j - 1];

	for (auto [v, x, y] : adj_compress[u]) {
		if (v == p) continue;

		height[v] = height[u] + 1;
		lca[v][0] = u;
		par[v] = iii(u, x, y);
		dfs2(v, u);
	}
}

void upd_go(int u, int v, int edge_id) {
	if (dir[ii(u, v)]) ans[edge_id] = 'R';
	else ans[edge_id] = 'L';	
}

int cal_lca(int u, int v) {
	if (height[u] > height[v]) swap(u, v);
	for (int j = 20; j >= 0; j--)
		if (height[lca[v][j]] >= height[u])
			v = lca[v][j];
	if (u == v) return u;
	for (int j = 20; j >= 0; j--)
		if (lca[u][j] != lca[v][j]) {
			u = lca[u][j];
			v = lca[v][j];
		}
	return lca[u][0];			
}

int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);

		dir[ii(u, v)] = true;
		cnt[ii(u, v)]++; cnt[ii(v, u)]++;
		org[ii(u, v)] = org[ii(v, u)] = i;
	}

	for (int i = 1; i <= n; i++)
		if (!cur[i])
			dfs(i);

	cerr << "--------------------------------" << '\n';

	top = 0;
	for (int i = 1; i <= n; i++)
		if (!id[i]) {
			++top;
			compress(i);
		}	

	for (int i = 1; i <= top; i++) cur[i] = 0;
	for (int i = 1; i <= top; i++)
		if (!cur[i]) {
			height[i] = 1;
			dfs2(i);
		}						
	
	cerr << "--------------------------------" << '\n';

	for (int i = 1; i <= top; i++) upd[i] = ii(1e9, 0);
	int q; cin >> q;
	while (q--) {
		int u, v; cin >> u >> v;
		u = id[u], v = id[v];

		int p = cal_lca(u, v);

		cerr << u << ' ' << v << ' ' << p << '\n';

		upd[u] = min(upd[u], ii(height[p], 0));
		upd[v] = min(upd[v], ii(height[p], 1));
	}

	cerr << "--------------------------------" << '\n';

	vector<ii> ord;
	for (int i = 1; i <= top; i++)
		ord.emplace_back(height[i], i);
	for (int i = 1; i <= m; i++)	
		ans[i] = 'B';

	sort(ord.begin(), ord.end(), greater<ii>());

	for (auto [h, u] : ord) {
		auto [cur_h, type] = upd[u];
		auto [p, x, y] = par[u];

		if (cur_h >= h) continue;

		upd[p] = min(upd[p], upd[u]);

		int edge_id = org[ii(x, y)];

		cerr << "cur_u: " << u << ", " << x << ' ' << y << ' ' << edge_id << ' ' << type << '\n';

		if (!type) upd_go(y, x, edge_id);
		else upd_go(x, y, edge_id);
	}

	for (int i = 1; i <= m; i++)
		cout << ans[i];
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10748 KB Output is correct
3 Correct 5 ms 11100 KB Output is correct
4 Correct 13 ms 11360 KB Output is correct
5 Correct 19 ms 11356 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 19 ms 11344 KB Output is correct
8 Correct 16 ms 11100 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Correct 8 ms 10848 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10748 KB Output is correct
3 Correct 5 ms 11100 KB Output is correct
4 Correct 13 ms 11360 KB Output is correct
5 Correct 19 ms 11356 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 19 ms 11344 KB Output is correct
8 Correct 16 ms 11100 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Correct 8 ms 10848 KB Output is correct
11 Correct 320 ms 48468 KB Output is correct
12 Correct 342 ms 50528 KB Output is correct
13 Correct 369 ms 53588 KB Output is correct
14 Correct 547 ms 60036 KB Output is correct
15 Correct 647 ms 63380 KB Output is correct
16 Correct 1243 ms 71900 KB Output is correct
17 Correct 1712 ms 77140 KB Output is correct
18 Correct 1252 ms 72088 KB Output is correct
19 Correct 1690 ms 79508 KB Output is correct
20 Correct 319 ms 50892 KB Output is correct
21 Correct 290 ms 49172 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10748 KB Output is correct
3 Correct 5 ms 11100 KB Output is correct
4 Correct 13 ms 11360 KB Output is correct
5 Correct 19 ms 11356 KB Output is correct
6 Correct 4 ms 10844 KB Output is correct
7 Correct 19 ms 11344 KB Output is correct
8 Correct 16 ms 11100 KB Output is correct
9 Correct 4 ms 11100 KB Output is correct
10 Correct 8 ms 10848 KB Output is correct
11 Correct 320 ms 48468 KB Output is correct
12 Correct 342 ms 50528 KB Output is correct
13 Correct 369 ms 53588 KB Output is correct
14 Correct 547 ms 60036 KB Output is correct
15 Correct 647 ms 63380 KB Output is correct
16 Correct 1243 ms 71900 KB Output is correct
17 Correct 1712 ms 77140 KB Output is correct
18 Correct 1252 ms 72088 KB Output is correct
19 Correct 1690 ms 79508 KB Output is correct
20 Correct 319 ms 50892 KB Output is correct
21 Correct 290 ms 49172 KB Output is correct
22 Execution timed out 3073 ms 83108 KB Time limit exceeded
23 Halted 0 ms 0 KB -