oj.uz

Submission #938381

# Submission time Handle Problem Language Result Execution time Memory
938381 2024-03-05T05:28:08 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 11 ms 636 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 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);
	vector<int> used(n+1, 0);
	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;
		used[v] = 1;
		int flag = 0;
		for(int to : g[v]){
			if(to == p) continue;
			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]){
			mp[make_pair(min(v, p), max(v, p))] = 1;
		}
	};
	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();
	};
	
	for(auto [a, b] : Q){
		path.clear();
		check.clear();
		for(int i = 1;i <= n; i++) used[i] = 0;
		dfs(a, b);
		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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 11 ms 600 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 9 ms 636 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Incorrect 3 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 11 ms 600 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 9 ms 636 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Incorrect 3 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 11 ms 600 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 9 ms 636 KB Output is correct
8 Correct 6 ms 348 KB Output is correct
9 Incorrect 3 ms 348 KB Output isn't correct
10 Halted 0 ms 0 KB -