oj.uz

Submission #918906

# Submission time Handle Problem Language Result Execution time Memory
918906 2024-01-30T17:44:29 Z Taxiradio One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3000 ms 344 KB 
// Source: https://usaco.guide/general/io

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

int n , m; 

vector<vector<int>> g , u;
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');
	u.resize(n , vector<int>(n , 0));
	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]){
				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.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3036 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -