oj.uz

Submission #938481

# Submission time Handle Problem Language Result Execution time Memory
938481 2024-03-05T07:48:48 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
0 / 100
 1 ms 344 KB 
#include "bits/stdc++.h"
 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
 
using namespace __gnu_pbds; 
 
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define ordered_mset tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 

const int INF = 1e18,N = 1001;
 
vector<vector<pair<int,int>>> g(N);

vector<int> vis(N);

void dfs(int n,int wow){
	vis[n] = 1;
	for(auto [v,ind] : g[n]){
		if(vis[v] != 1 && wow != ind){
			dfs(v,wow);
		}
	}
}

bool R = 0,L = 0;

void checkRL(int n,int wow,int a,int b){
	
	if(n == a){
		R = 1;
	} else if(n == b){
		L = 1;
	}
	vis[n] = 1;
	for(auto [v,ind] : g[n]){
		if(vis[v] != 1 && wow != ind){
			checkRL(v,wow,a,b);
		}
	}
	
} 

void solve(){	
	
	int n,m;
	cin >> n >> m;
	vector<pair<int,int>> rebro;
	for(int i = 0;i < m;i++){
		int a,b;
		cin >> a >> b;
		rebro.pb({a,b});
		g[a].pb({b,i});
		g[b].pb({a,i});
	}
	vector<pair<int,int>> vip;
	int p;
	cin >> p;
	for(int i = 0;i < p;i++){
		int a,b;
		cin >> a >> b;
		vip.pb({a,b});
	}
	int i = 0;
	vector<int> r(n + 1,1),l(n + 1,1);
	for(auto [u,v] : rebro){
		for(auto [fst,scn] : vip){
			for(int j = 0;j < N;j++){
				vis[j] = 0;
			}
			
			dfs(fst,i);
			if(vis[scn]){
				continue;
			}
			R = 0;
			L = 0;
			for(int j = 0;j < N;j++){
				vis[j] = 0;
			}
			checkRL(fst,i,u,v);
			if(R){
				r[i] = 1;
				l[i] = 0;
			}
			if(L){
				l[i] = 1;
				r[i] = 0;
			}
		}
		i++;
	}
	string ans = "";
	for(int i = 0;i < m;i++){
		if(r[i] && l[i]){
			ans += 'B';
		} else if(r[i]){
			ans += 'R';
		} else{
			ans += 'L';
		}
	}
	cout << ans << "\n";
	
}
 
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
//	cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -