Submission #938968

#	Time	Username	Problem	Language	Result	Execution time	Memory
938968		iskhakkutbilim	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	0 ms	348 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);
	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});
	}
	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, -1);
	vector<int> tin(n+1), tout(n+1);
	vector<int> ans(m, -1);
	vector<int> used(n+1, 0);
	int timer = 0;
	map<pair<int, int>, int> mp;
	function<void(int, int)> bridges=[&](int v, int p){
		tin[v] = ++timer;
		out[v] = timer;
		used[v] = 1;
		int flag = 0;
		for(auto [to, idx] : g[v]){
			if(make_pair(v, to) == edge[idx]) dir[idx] = 1;
			if(!used[to]){
				bridges(to, v);
				out[v] = min(out[v], out[to]);
			}else{
				if(to == p){
					if(flag){
						out[v] = min(out[v], tin[to]);
					}
					flag = 1;
				}else{
					out[v] = min(out[v], tin[to]);
				}
			}
		}
		if(p != -1 && tin[v] == out[v]){
			mp[make_pair(min(v, p), max(v, p))] = 1;
		}
		tout[v] = timer;
	};
	for(int i = 1;i <= n; i++){
		if(!used[i]){
			bridges(i, -1);
		}
	}
	for(int i = 1;i <= n; i++) used[i] = 0;
	pair<int, int> mn[n+1], mx[n+1];
	function<void(int, int)> dfs=[&](int v, int p){
		used[v] = 1;
		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;
		for(auto [to, idx] : g[v]){
			if(used[to]) continue;
			dfs(to, v);
			mn[v] = min(mn[v], mn[to]);
			mx[v] = max(mx[v], mx[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(!used[i]) dfs(i, i);
	}
	
	for(int i = 0;i < m; i++){
		auto [a, b] = edge[i];
		if(a > b) swap(a, b);
		if(!mp.count({a, b})){
			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: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40