oj.uz

Submission #938979

# Submission time Handle Problem Language Result Execution time Memory
938979 2024-03-06T02:29:50 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 343 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 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 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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 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 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 191 ms 21208 KB Output is correct
12 Correct 176 ms 23496 KB Output is correct
13 Correct 219 ms 26560 KB Output is correct
14 Correct 229 ms 29016 KB Output is correct
15 Correct 226 ms 29472 KB Output is correct
16 Correct 215 ms 26060 KB Output is correct
17 Correct 219 ms 29380 KB Output is correct
18 Correct 220 ms 26164 KB Output is correct
19 Correct 202 ms 31944 KB Output is correct
20 Correct 199 ms 23748 KB Output is correct
21 Correct 151 ms 22532 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 2 ms 604 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 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 191 ms 21208 KB Output is correct
12 Correct 176 ms 23496 KB Output is correct
13 Correct 219 ms 26560 KB Output is correct
14 Correct 229 ms 29016 KB Output is correct
15 Correct 226 ms 29472 KB Output is correct
16 Correct 215 ms 26060 KB Output is correct
17 Correct 219 ms 29380 KB Output is correct
18 Correct 220 ms 26164 KB Output is correct
19 Correct 202 ms 31944 KB Output is correct
20 Correct 199 ms 23748 KB Output is correct
21 Correct 151 ms 22532 KB Output is correct
22 Correct 274 ms 33764 KB Output is correct
23 Correct 264 ms 30404 KB Output is correct
24 Correct 343 ms 30516 KB Output is correct
25 Correct 270 ms 39880 KB Output is correct
26 Correct 275 ms 32964 KB Output is correct
27 Correct 256 ms 30496 KB Output is correct
28 Correct 94 ms 7088 KB Output is correct
29 Correct 258 ms 26860 KB Output is correct
30 Correct 226 ms 26956 KB Output is correct
31 Correct 244 ms 27780 KB Output is correct
32 Correct 202 ms 29172 KB Output is correct