oj.uz

Submission #1027405

# Submission time Handle Problem Language Result Execution time Memory
1027405 2024-07-19T05:55:56 Z BuzzyBeez One-Way Streets (CEOI17_oneway) C++17
100 / 100
 179 ms 64024 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
	
vector<pair<int, int>> adj[N + 8];
pair<int, int> E1[N + 8], E2[N + 8];

pair<int, int> fixed(int u, int v) {return {min(u, v), max(u, v)};}
map<pair<int, int>, int> F;

void add_edge(int u, int v, int id) {
	adj[u].push_back({v, id}); adj[v].push_back({u, id});
	++F[fixed(u, v)]; E1[id] = {u, v};
}

struct Disjoint_Set_Union {
	vector<int> par, sz;
	void init(int n) {
		par.assign(n + 8, 0); sz.assign(n + 8, 1);
		iota(par.begin(), par.end(), 0);
	}
	int find(int u) {return (par[u] == u ? u : (par[u] = find(par[u])));}
	bool join(int u, int v) {
		u = find(u); v = find(v);
		if (u == v) return 0;
		if (sz[u] < sz[v]) swap(u, v);
		par[v] = u; sz[u] += sz[v];
		return 1;
	}
} DSU;

int tin[N + 8], tout[N + 8], low[N + 8], d[N + 8];
pair<int, int> euler[N * 2 + 8];
pair<int, int> SpT[20][N * 2 + 8];
int dp[N + 8]; bool vis[N + 8];

void build_SpT(int n) {
	for (int lg = 0; (1 << lg) <= n; ++lg) for (int i = 1; i + (1 << lg) - 1 <= n; ++i) {
		if (!lg) SpT[lg][i] = euler[i];
		else SpT[lg][i] = min(SpT[lg - 1][i], SpT[lg - 1][i + (1 << (lg - 1))]);
	}
}

pair<int, int> rmq(int l, int r) {
	if (l > r) swap(l, r);
	int lg = __lg(r - l + 1);
	return min(SpT[lg][l], SpT[lg][r - (1 << lg) + 1]);
}

int LCA(int u, int v) {return rmq(tin[u], tin[v]).second;}

struct Solver {
	int timer; vector<tuple<int, int, int>> bridges;
	vector<pair<int, int>> Tadj[N + 8];
	Solver() {}
	
	void init(int n) {timer = 0; DSU.init(n);}
	
	void add_tree_edge(int u, int v, int id) {
		Tadj[u].push_back({v, id}); Tadj[v].push_back({u, id});
		// cout << u << ' ' << v << ' ' << id << '\n';
	}
	
	void DFS_build(int u, int p) {
		tin[u] = low[u] = ++timer;
		for (auto [v, id] : adj[u]) if (v != p) {
			if (tin[v]) low[u] = min(low[u], tin[v]);
			else {
				DFS_build(v, u); low[u] = min(low[u], low[v]);
				if (low[v] > tin[u] && F[fixed(u, v)] == 1) {
					bridges.push_back({u, v, id});
					// cout << u << " -> " << v << " is a bridge!!\n";
				}
				else DSU.join(u, v);
			}
		}
	}
	
	void DFS_EulerTour(int u, int p) {
		tin[u] = ++timer; euler[timer] = {d[u], u};
		for (auto [v, id] : Tadj[u]) if (v != p) {
			d[v] = d[u] + 1; DFS_EulerTour(v, u);
			euler[++timer] = {d[u], u};
		}
		tout[u] = timer;
	}
	
	void build_tree(int n) {
		for (int i = 1; i <= n; ++i) if (!tin[i]) DFS_build(i, i);
		for (auto [u, v, id] : bridges) add_tree_edge(DSU.find(u), DSU.find(v), id);
		timer = 0; 
		for (int i = 1; i <= n; ++i) if (!tout[i]) DFS_EulerTour(i, i);
		build_SpT(timer);
	}
	
	// u -> par[u] : -1; par[u] -> u: 1
	
	int A;
	void add_constraint(int u, int v) { // u --> v
		u = DSU.find(u); v = DSU.find(v);
		A = LCA(u, v);
		--dp[u]; ++dp[v]; 	
		// cout << "added constraint : " << u << " -> " << v << '\n';
	}
	
	void DFS_sweep(int u, int p) {
		vis[u] = 1;
		for (auto [v, id] : Tadj[u]) if (v != p) DFS_sweep(v, u), dp[u] += dp[v];
		// cout << u << ' ' << dp[u] << '\n';
	}
	
	void DFS_label(int u, int p) {
		for (auto [v, id] : Tadj[u]) if (v != p) {
			DFS_label(v, u);
			if (!dp[v]) continue;
			else {
				E1[id].first = DSU.find(E1[id].first); 
				E1[id].second = DSU.find(E1[id].second);
				if (dp[v] < 0) E2[id] = {v, u};
				else E2[id] = {u, v}; 
			}
		}
	}
	
	void solve(int n) {for (int i = 1; i <= n; ++i) if (!vis[i]) DFS_sweep(i, i),  DFS_label(i, i);}
} DS;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, u, v; cin >> n >> m; DS.init(n);
	for (int i = 1; i <= m; ++i) cin >> u >> v, add_edge(u, v, i);
	DS.build_tree(n);
	int q; cin >> q;
	while (q--) cin >> u >> v, DS.add_constraint(u, v);
	DS.solve(n);
	// for (int i = 1; i <= m; ++i) cout << E1[i].first << ' ' << E1[i].second << ' ' << E2[i].first << ' ' << E2[i].second << '\n';
	for (int i = 1; i <= m; ++i)
		if (!E2[i].first) cout << 'B';
		else if (E1[i] == E2[i]) cout << 'R';
		else cout << 'L';
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 7004 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 7004 KB Output is correct
11 Correct 65 ms 20776 KB Output is correct
12 Correct 74 ms 25328 KB Output is correct
13 Correct 77 ms 31824 KB Output is correct
14 Correct 108 ms 39740 KB Output is correct
15 Correct 106 ms 42244 KB Output is correct
16 Correct 139 ms 52168 KB Output is correct
17 Correct 131 ms 56264 KB Output is correct
18 Correct 139 ms 52092 KB Output is correct
19 Correct 118 ms 59332 KB Output is correct
20 Correct 61 ms 27984 KB Output is correct
21 Correct 61 ms 27472 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 5212 KB Output is correct
3 Correct 3 ms 5468 KB Output is correct
4 Correct 3 ms 5588 KB Output is correct
5 Correct 3 ms 5468 KB Output is correct
6 Correct 3 ms 5468 KB Output is correct
7 Correct 3 ms 5468 KB Output is correct
8 Correct 3 ms 5468 KB Output is correct
9 Correct 3 ms 5212 KB Output is correct
10 Correct 3 ms 7004 KB Output is correct
11 Correct 65 ms 20776 KB Output is correct
12 Correct 74 ms 25328 KB Output is correct
13 Correct 77 ms 31824 KB Output is correct
14 Correct 108 ms 39740 KB Output is correct
15 Correct 106 ms 42244 KB Output is correct
16 Correct 139 ms 52168 KB Output is correct
17 Correct 131 ms 56264 KB Output is correct
18 Correct 139 ms 52092 KB Output is correct
19 Correct 118 ms 59332 KB Output is correct
20 Correct 61 ms 27984 KB Output is correct
21 Correct 61 ms 27472 KB Output is correct
22 Correct 144 ms 56276 KB Output is correct
23 Correct 179 ms 52108 KB Output is correct
24 Correct 147 ms 52164 KB Output is correct
25 Correct 146 ms 64024 KB Output is correct
26 Correct 155 ms 55164 KB Output is correct
27 Correct 148 ms 52388 KB Output is correct
28 Correct 33 ms 11344 KB Output is correct
29 Correct 79 ms 26964 KB Output is correct
30 Correct 90 ms 27472 KB Output is correct
31 Correct 77 ms 28244 KB Output is correct
32 Correct 125 ms 38480 KB Output is correct