oj.uz

Submission #958443

# Submission time Handle Problem Language Result Execution time Memory
958443 2024-04-05T19:27:31 Z dio_2 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 461 ms 61616 KB 
#include<bits/stdc++.h>
using namespace std;

using pii = pair<int, int>;

// DESCRIPTION
// Given an undirected graph returns a forest 
// where every node in a tree is a potential SCC in the initial graph.
// Works with multi-edges and disconnected components.
// Doesnt acctually orient the edges to make the SCC since 
// The forest only considers them as nodes.
// You don't really have a connection with the previous graph.
// 0 - indexed.
// check: https://codeforces.com/contest/555/problem/E.
// Watch out for:
// 1) multi-edges.
// 2) how many components.
// 3) carefull implementation.
vector<vector<int>> Get2EdgeForest(vector<vector<pii>> &g, int n, int m, int &N, vector<int> &labels, vector<pii> &bri){
	vector<int> vis(n), dep(n), is_span(m), dp(n), is_bridge(m);
	vector<vector<int>> gA(n), gB(n);
	vector<pii> bridges;
	
	// finding bridges and marking them
	auto dfs = [&](auto &&dfs, int u, int p, int id)->void{
		vis[u] = 1;
		for(auto [v, i] : g[u]) if(!vis[v]){
			dep[v] = dep[u] + 1;
			is_span[i] = 1;
			dfs(dfs, v, u, i); // DFS AFTER DEPTH CALCULATION!!!!!!!.
		}
		int cnt_par = 0;
		set<int> s; // UGLY with sets can be done without ' em.
		for(auto [v, i] : g[u]){ 
			if(v == p){
				cnt_par += 1;
				continue;
			}
			if(s.count(v)) continue;
			s.insert(v);
			if(is_span[i]) dp[u] += dp[v];
			if(!is_span[i] && dep[v] > dep[u]) dp[u]--;
			if(!is_span[i] && dep[v] < dep[u]) dp[u]++;
		}
		// cnt_par == 1 needed for multiple edges.
		if(dp[u] == 0 && p != -1 && cnt_par == 1){
			bridges.emplace_back(u, p);
			is_bridge[id] = 1;
		}
	}; 
	
	for(int i = 0;i < n;i++){
		if(!vis[i]){
			dfs(dfs, i, -1, -1);
		}
	}
	
	// ceating a second graph without bridges
	for(int i = 0;i < n;i++){
		for(auto [j, id] : g[i]){
			if(is_bridge[id]) continue;
			gA[i].push_back(j);
		}
	}

	vector<int> label(n);
	fill(vis.begin(), vis.end(), false);
	int cnt = 0;
	
	// merge nodes.
	auto dfs2 = [&](auto &&dfs2, int u)->void{
		vis[u] = 1;
		label[u] = cnt;
		for(int v : gA[u]){
			if(!vis[v]){
				dfs2(dfs2, v);
			}
		}
	};
	
	for(int i = 0;i < n;i++){
		if(!vis[i]){
			dfs2(dfs2, i);
			cnt++;
		}
	}
	
	// create the tree.
	for(auto [u, v] : bridges){
		int orgu = u, orgv = v;
		u = label[u];
		v = label[v];
		if(u == v) continue;
		bri.emplace_back(orgu, orgv);
		gB[u].push_back(v);
		gB[v].push_back(u);
	}
	
	N = cnt;
	labels = label;
	return gB;
}


int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n, m;
	cin >> n >> m;
	
	vector<vector<pair<int, int>>> g(n);
	vector<pii> E(m);
	string ans(m, 'B');
	for(int i = 0;i < m;i++){
		int a, b;
		cin >> a >> b, --a, --b;
		if(a == b){
			ans[i] = 'B';
		} else {
			g[a].emplace_back(b, i);
			g[b].emplace_back(a, i);
		}
		E[i] = make_pair(a, b);
	}
	
	int p;
	cin >> p;
	vector<pair<int, int>> a(p);
	for(int i = 0;i < p;i++){
		int x, y;
		cin >> x >> y, --x, --y;
		a[i] = make_pair(x, y);
	}
	
	int N;
	vector<int> labels;
	vector<pii> bri;
	map<pii, pii> mapka;
	map<pii, pii> ord;
	map<pii, bool> is;
	vector<vector<int>> new_g = Get2EdgeForest(g, n, m, N, labels, bri);
	vector<bool> vis(N);
	
	for(auto [x, y] : bri){
		mapka[make_pair(labels[x], labels[y])] = make_pair(x, y);
		is[make_pair(x, y)] = true;
	}
	const int LOG = 20;
	vector<vector<int>> up(N, vector<int> (LOG));
	vector<int> dep(N);
	vector<int> L(N), A(N), B(N);
	auto dfs = [&](auto &&dfs, int u, int p)->void{
		vis[u] = 1;
		for(int v : new_g[u]) if(v != p){
			dep[v] = dep[u] + 1;
			up[v][0] = u;
			for(int i = 1;i < LOG;i++) up[v][i] = up[ up[v][i - 1] ][i - 1];
			dfs(dfs, v, u);
		}
	};
	
	auto lca = [&](int u, int v)->int{
		if(dep[u] > dep[v]) swap(v, u);
		int k = dep[v] - dep[u];
		for(int i = LOG - 1;i >= 0;i--){
			if((k >> i) & 1) v = up[v][i];
		}
		assert(dep[v] == dep[u]);
		if(v == u) return v;
		for(int i = LOG - 1;i >= 0;i--){
			if(up[v][i] != up[u][i]){
				u = up[u][i];
				v = up[v][i];
			}
		}
		assert(up[v][0] == up[u][0]);
		return up[v][0];
	};
	
	for(int i = 0;i < N;i++){
		if(!vis[i]){
			for(int j = 0;j < LOG;j++) up[i][j] = i;
			dfs(dfs, i, -1);
		}
	}
	
	for(auto &[x, y] : a){ // x -> y.
		x = labels[x];
		y = labels[y];
		int l = lca(x, y);
		if(x == y) continue;
		L[l]++;
		A[x]++;
		B[y]++;
	}
	
	auto dfs2 = [&](auto &&dfs2, int u, int p)->void{
		for(int v : new_g[u]) if(v != p){
			dfs2(dfs2, v, u);
			A[u] += A[v];
			B[u] += B[v];
			L[u] += L[v];
		}
		if(p != -1){
			assert(not(A[u] - L[u] > 0 && B[u] - L[u] > 0));
			pii real;
			if(mapka.find(make_pair(u, p)) != mapka.end()){
				real = mapka[make_pair(u, p)];
			} else {
				real = mapka[make_pair(p, u)];
			}
			int _a = real.first;
			int _b = real.second;
			if(labels[_a] != p) swap(_a, _b);
			// _a is parent _b in bridge tree.
			if(A[u] - L[u] > 0){
				ord[real] = make_pair(_b, _a);
			} else if(B[u] - L[u] > 0){
				ord[real] = make_pair(_a, _b);
			} else {
				ord[real] = make_pair(-1, -1);
			}
		}
	};
	
	for(int i = 0;i < N;i++){
		if(dep[i] == 0){
			dfs2(dfs2, i, -1);
		}
	}
	
	for(int i = 0;i < m;i++){
		int _a = E[i].first;
		int _b = E[i].second;
		if(is[make_pair(_a, _b)]){
			if(ord[make_pair(_a, _b)].first == -1) continue;
			if(ord[make_pair(_a, _b)] != make_pair(_a, _b)){
				ans[i] = 'L';
			} else {
				ans[i] = 'R';
			}
		} else if(is[make_pair(_b, _a)]){
			swap(_a, _b);
			if(ord[make_pair(_a, _b)].first == -1) continue;
			if(ord[make_pair(_a, _b)] != make_pair(_a, _b)){
				ans[i] = 'R';
			} else {
				ans[i] = 'L';
			}
		}
	}
	
	cout << ans;
	
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 488 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 488 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 140 ms 20644 KB Output is correct
12 Correct 156 ms 22864 KB Output is correct
13 Correct 148 ms 26476 KB Output is correct
14 Correct 176 ms 33812 KB Output is correct
15 Correct 185 ms 36736 KB Output is correct
16 Correct 407 ms 50608 KB Output is correct
17 Correct 349 ms 53816 KB Output is correct
18 Correct 380 ms 50556 KB Output is correct
19 Correct 367 ms 56020 KB Output is correct
20 Correct 119 ms 22940 KB Output is correct
21 Correct 113 ms 22004 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 488 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 3 ms 860 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 856 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 140 ms 20644 KB Output is correct
12 Correct 156 ms 22864 KB Output is correct
13 Correct 148 ms 26476 KB Output is correct
14 Correct 176 ms 33812 KB Output is correct
15 Correct 185 ms 36736 KB Output is correct
16 Correct 407 ms 50608 KB Output is correct
17 Correct 349 ms 53816 KB Output is correct
18 Correct 380 ms 50556 KB Output is correct
19 Correct 367 ms 56020 KB Output is correct
20 Correct 119 ms 22940 KB Output is correct
21 Correct 113 ms 22004 KB Output is correct
22 Correct 461 ms 55688 KB Output is correct
23 Correct 455 ms 52324 KB Output is correct
24 Correct 460 ms 52520 KB Output is correct
25 Correct 411 ms 61616 KB Output is correct
26 Correct 448 ms 54952 KB Output is correct
27 Correct 438 ms 52628 KB Output is correct
28 Correct 51 ms 6660 KB Output is correct
29 Correct 140 ms 24304 KB Output is correct
30 Correct 142 ms 24220 KB Output is correct
31 Correct 140 ms 24992 KB Output is correct
32 Correct 200 ms 34160 KB Output is correct