Submission #918905

#	Time	Username	Problem	Language	Result	Execution time	Memory
918905		Taxiradio	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	3040 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 u[n][n];
	for(int i = 0; i < n; i++){
		for(int i2 = 0; i2 < n; i2++){
			u[i][i2] = 0;
		}
	}
	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]){
				u[a][parents[a]] = 1;
				u[parents[a]][a] = 2;
				u[b][parents[b]] = 2;
				u[parents[b]][b] = 1;
				a = parents[a];
				b = parents[b];
				continue;
			}
			a = l[a];
			b = l[b];
		}
	}
	for(int i = 0; i < m; i++){
		if(u[o[i][0]][o[i][1]] == 0)cout << "B";
		if(u[o[i][0]][o[i][1]] == 1)cout << "R";
		if(u[o[i][0]][o[i][1]] == 2)cout << "L";
	}
	cout << endl;
}

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