Submission #938980

#	Time	Username	Problem	Language	Result	Execution time	Memory
938980		iskhakkutbilim	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	306 ms	39880 KiB

oneway

#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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40