oj.uz

답안 #918898

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
918898 2024-01-30T17:31:30 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;
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.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3021 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3021 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3021 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -