oj.uz

Submission #1027406

# Submission time Handle Problem Language Result Execution time Memory
1027406 2024-07-19T05:56:09 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 160 ms 63952 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 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 3 ms 9052 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 5208 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 3 ms 9052 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 5208 KB Output is correct
11 Correct 61 ms 20564 KB Output is correct
12 Correct 68 ms 26964 KB Output is correct
13 Correct 78 ms 32004 KB Output is correct
14 Correct 116 ms 39760 KB Output is correct
15 Correct 105 ms 42396 KB Output is correct
16 Correct 133 ms 52428 KB Output is correct
17 Correct 129 ms 56260 KB Output is correct
18 Correct 126 ms 52168 KB Output is correct
19 Correct 148 ms 59340 KB Output is correct
20 Correct 72 ms 28024 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 2 ms 8792 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 3 ms 9052 KB Output is correct
4 Correct 3 ms 9052 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 3 ms 9052 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 5208 KB Output is correct
11 Correct 61 ms 20564 KB Output is correct
12 Correct 68 ms 26964 KB Output is correct
13 Correct 78 ms 32004 KB Output is correct
14 Correct 116 ms 39760 KB Output is correct
15 Correct 105 ms 42396 KB Output is correct
16 Correct 133 ms 52428 KB Output is correct
17 Correct 129 ms 56260 KB Output is correct
18 Correct 126 ms 52168 KB Output is correct
19 Correct 148 ms 59340 KB Output is correct
20 Correct 72 ms 28024 KB Output is correct
21 Correct 61 ms 27472 KB Output is correct
22 Correct 147 ms 56352 KB Output is correct
23 Correct 145 ms 52052 KB Output is correct
24 Correct 152 ms 52104 KB Output is correct
25 Correct 160 ms 63952 KB Output is correct
26 Correct 145 ms 55236 KB Output is correct
27 Correct 159 ms 52372 KB Output is correct
28 Correct 31 ms 11344 KB Output is correct
29 Correct 78 ms 27056 KB Output is correct
30 Correct 75 ms 27480 KB Output is correct
31 Correct 79 ms 28256 KB Output is correct
32 Correct 103 ms 38416 KB Output is correct