Submission #938376

#	Time	Username	Problem	Language	Result	Execution time	Memory
938376		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	11 ms	604 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 7
5 5
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

signed main(){
	int n, m; cin >> n >> m;
	vector<int> g[n+1];
	vector<pair<int, int> > edge;
	for(int i = 1;i <= m; i++){
		int a, b; cin >> a >> b;
		edge.push_back({a, b});
		g[a].push_back(b);
		g[b].push_back(a);
	}
	int q; cin >> q;
	vector<pair<int, int> > Q(q);
	for(int i = 0;i < q; i++){
		cin >> Q[i].ff >> Q[i].ss;
	}
	vector<int> in(n+1, -1), out(n+1, -1);
	vector<char> ans(m, '#');
	vector<int> par(n+1);
	int timer = 1;
	map<pair<int, int>, int> mp;
	function<void(int, int)> bridges=[&](int v, int p){
		in[v] = timer;
		out[v] = timer++;
		par[v] = p;
		int flag = 0;
		for(int to : g[v]){
			if(to == p) continue;
			if(in[to] == -1){
				bridges(to, v);
				out[v] = min(out[v], out[to]);
			}else{
				if(to == p){
					if(flag){
						out[v] = min(out[v], in[to]);
					}
					flag = 1;
				}else
				out[v] = min(out[v], in[to]);
			}
		}
		if(p != -1 && in[v] == out[v]){
			mp[make_pair(min(v, p), max(v, p))] = 1;
		}
	};
	for(int i = 1;i <= n; i++){
		if(in[i] == -1){
			bridges(i, -1);
		}
	}
	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] = 'B';
		}
	}
	vector<int> path;
	vector<int> used(n+1, 0);
	int ok = 0;
	function<void(int, int)> dfs=[&](int v, int finish){
		if(ok) return;
		path.push_back(v);
		used[v] = 1;
		if(v == finish){
			ok = 1;
			return;
		}
		for(int to : g[v]){
			if(used[to]) continue;
			dfs(to, finish);
		}
		if(ok) return;
		path.pop_back();
	};
	
	for(auto [a, b] : Q){
		path.clear();
		ok = 0;
		for(int i = 1;i <= n; i++) used[i] = 0;
		dfs(a, b);
		if(!ok) assert(false);
		set<pair<int, int> > st;
		
		for(int i = 0;i + 1 < (int)path.size(); i++){
			st.insert(make_pair(path[i], path[i+1]));
		}
	
		for(int i = 0;i < m; i++){
			if(ans[i] != '#') continue;
			if(st.count(edge[i])){
				ans[i] = 'R';
			}else if(st.count({edge[i].ss, edge[i].ff})){
				ans[i] = 'L';
			}
		}
	}
	
	for(int i = 0;i < m; i++){
		if(ans[i] == '#') ans[i] = 'B';
		cout << ans[i];
	}
	
	
	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40