Submission #938390

#	Time	Username	Problem	Language	Result	Execution time	Memory
938390		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3020 ms	21820 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 5
1 2
1 2
4 3
2 3
4 5
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);
	vector<int> used(n+1, 0);
	int timer = 1;
	map<pair<int, int>, int> mp;
	//cout << "bridges : " << '\n';
	function<void(int, int)> bridges=[&](int v, int p){
		in[v] = timer;
		out[v] = timer++;
		par[v] = p;
		used[v] = 1;
		int flag = 0;
		for(int to : g[v]){
			
			if(!used[to]){
				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]){
			//cout << v << ' ' << p << '\n';
			mp[make_pair(min(v, p), max(v, p))] = 1;
		}
	};
	//cout << '\n';
	for(int i = 1;i <= n; i++){
		if(!used[i]){
			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, check;
	
	function<void(int, int)> dfs=[&](int v, int finish){
		check.push_back(v);
		used[v] = 1;
		if(v == finish){
			path = check;
			return;
		}
		for(int to : g[v]){
			if(used[to]) continue;
			dfs(to, finish);
		}
		check.pop_back();
	};
	set<pair<int, int> > st;
	for(auto [a, b] : Q){
		path.clear();
		check.clear();
		for(int i = 1;i <= n; i++) used[i] = 0;
		dfs(a, b);
		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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40