oj.uz

Submission #938980

# Submission time Handle Problem Language Result Execution time Memory
938980 2024-03-06T02:31:22 Z iskhakkutbilim One-Way Streets (CEOI17_oneway) C++17
100 / 100
 306 ms 39880 KB 
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int N = 2e5;
const int mod = 1e9 + 7;

/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/
// BBRBBL
signed main(){
	int n, m; cin >> n >> m;
	vector<pair<int, int> > g[n+1];
	vector<pair<int, int> > edge;
	vector<int> dir(m, 0);
	map<pair<int, int>, int> mp;
	for(int i = 0;i < m; i++){
		int a, b; cin >> a >> b;
		edge.push_back({a, b});
		g[a].push_back({b, i});
		g[b].push_back({a, i});
		mp[{a, b}]++;
		mp[{b, a}]++;
	}
	int q; cin >> q;
	vector<pair<int, int> > Q(q);
	vector<pair<int, int>> vert[n+1];
	for(int i = 0;i < q; i++){
		cin >> Q[i].ff >> Q[i].ss;
		vert[Q[i].ff].push_back({Q[i].ss, 0});
		vert[Q[i].ss].push_back({Q[i].ff, 1});
	}
	vector<int>  out(n+1, 0);
	vector<int> tin(n+1), tout(n+1);
	vector<int> ans(m, -1);
	vector<int> used(n+1, 0);
	int timer = 0;
	function<void(int, int)> timers=[&](int v, int p){
		tin[v] = ++timer;
		used[v] = 1;
		for(auto [to, idx] : g[v]){
			if(!used[to] && to != p){
				if(make_pair(v, to) == edge[idx]) dir[idx] = 1;
				timers(to, v);
			}
		}
		tout[v] = timer;
	};
	for(int i = 1;i <= n; i++){
		if(!used[i]){
			timers(i, -1);
		}
	}
	
	pair<int, int> mn[n+1], mx[n+1];
	function<void(int, int)> dfs=[&](int v, int p){
		
		mn[v] = {n+1, -1};
		mx[v] = {-1, -1};
		for(auto [u, t] : vert[v]){
			mn[v] = min(mn[v], make_pair(tin[u], t));
			mx[v] = max(mx[v], make_pair(tout[u], t));
		}
		vector<pair<int, int> > tmp;
		out[v] = tin[v];
		for(auto [to, idx] : g[v]){
			if(to != p){
				if(out[to]){
					out[v] = min(out[v], out[to]);
				}else{
					dfs(to, v);
					mn[v] = min(mn[v], mn[to]);
					mx[v] = max(mx[v], mx[to]);
					out[v] = min(out[v], out[to]);
					if(out[to] > tin[v]){
						tmp.push_back({to, idx});
					}	
				}
			}
		}
		for(auto [to, idx] : tmp){
			if(mn[to].ff < tin[to]){
				ans[idx] = mn[to].ss;
			}
			if(mx[to].ff > tout[to]){
				ans[idx] = mx[to].ss;
			}
		}
		
	};
	for(int i = 1;i <= n; i++){
		if(!out[i]) dfs(i, i);
	}
	
	for(int i = 0;i < m; i++){
		auto [a, b] = edge[i];
		if(mp[{a, b}] > 1){
			ans[i] = -1;
		}
	}
	for(int i = 0;i < m; i++){
		if(ans[i] == -1){
			cout << 'B';
		}else{
			ans[i]^= dir[i];
			if(ans[i] > 0) cout << 'L';
			else cout << 'R';
		}
	}
	
	
	return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 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 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 158 ms 21112 KB Output is correct
12 Correct 176 ms 23496 KB Output is correct
13 Correct 216 ms 26444 KB Output is correct
14 Correct 237 ms 28848 KB Output is correct
15 Correct 212 ms 29384 KB Output is correct
16 Correct 221 ms 26232 KB Output is correct
17 Correct 204 ms 29540 KB Output is correct
18 Correct 220 ms 26056 KB Output is correct
19 Correct 193 ms 31828 KB Output is correct
20 Correct 172 ms 23748 KB Output is correct
21 Correct 145 ms 22600 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 158 ms 21112 KB Output is correct
12 Correct 176 ms 23496 KB Output is correct
13 Correct 216 ms 26444 KB Output is correct
14 Correct 237 ms 28848 KB Output is correct
15 Correct 212 ms 29384 KB Output is correct
16 Correct 221 ms 26232 KB Output is correct
17 Correct 204 ms 29540 KB Output is correct
18 Correct 220 ms 26056 KB Output is correct
19 Correct 193 ms 31828 KB Output is correct
20 Correct 172 ms 23748 KB Output is correct
21 Correct 145 ms 22600 KB Output is correct
22 Correct 269 ms 33648 KB Output is correct
23 Correct 255 ms 30528 KB Output is correct
24 Correct 306 ms 30660 KB Output is correct
25 Correct 244 ms 39880 KB Output is correct
26 Correct 267 ms 32748 KB Output is correct
27 Correct 265 ms 30584 KB Output is correct
28 Correct 95 ms 7084 KB Output is correct
29 Correct 233 ms 26824 KB Output is correct
30 Correct 238 ms 26956 KB Output is correct
31 Correct 252 ms 27848 KB Output is correct
32 Correct 198 ms 29308 KB Output is correct