Submission #918898

#	Time	Username	Problem	Language	Result	Execution time	Memory
918898		Taxiradio	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3021 ms	344 KiB

oneway

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

int n , m; 

vector<vector<int>> g;
vector<int> l , times , parents;
vector<bool> vis;
vector<array<int , 2>> o;
int timer = 0;

void dfs(int h , int p){
	vis[h] = true;
	parents[h] = p;
	times[h] = timer++;
	l[h] = times[h];
	for(int x:g[h]){
		if(x==p)continue;
		if(vis[x]){
			l[h] = min(l[h] , times[x]);
		}else{
			dfs(x , h);
			l[h] = min(l[h] , l[x]);
		}
		
	} 
}

int main() {
	ios_base::sync_with_stdio(false);
	string ans;
	cin.tie(0);
	cin >> n >> m;
	g.resize(n);
	l.resize(n);
	times.resize(n);
	vis.resize(n);
	parents.resize(n);
	ans.resize(m , 'B');
	for(int i = 0; i < m; i++){
		int a , b; cin >> a >> b;
		o.push_back({a-1 , b-1});
		g[a-1].push_back(b-1);
		g[b-1].push_back(a-1);
	}
	dfs(0 , -1);
	int k; cin >> k;
	for(int i = 0; i < k; i++){
		int a , b; cin >> a >> b;
		a--; b--;
		while(a != b){
			if(a == l[a] && b == l[b]){
				for(int i = 0; i < m; i++){
					if(o[i][0] == a && o[i][1] == parents[a]){
						ans[i] = 'R';
					}
					if(o[i][1] == a && o[i][2] == parents[a]){
						ans[i] = 'L';
					}
					if(o[i][0] == b && o[i][1] == parents[b]){
						ans[i] = 'L';
					}
					if(o[i][1] == b && o[i][0] == parents[b]){
						ans[i] = 'R';
					}
				}
				a = parents[a];
				b = parents[b];
				continue;
			}
			a = l[a];
			b = l[b];
		}
	}
	cout << ans << endl;
}

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