oj.uz

답안 #878648

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
878648 2023-11-25T03:17:50 Z Jawad_Akbar_JJ One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3 ms 9560 KB 
#include <iostream>
#include <vector>
#include <map>

using namespace std;

const int N = 1e5  + 10;
vector<vector<int>> nei[N];
map<int,int> seen[N];
int ans[N];
int Seen[N];
int mn[N];
bool cyc[N];
int h[N];
int T = 1;
int inf = 1e9;
int target;
int U[N],V[N];






bool Dfs(int u){
	
	if (u==target)
		return true;
	if (Seen[u] == T)
		return false;
	
		
	Seen[u] = T;
	for (vector<int> v : nei[u]){
		int i = v[0];
		int t = v[1];
		int ind = v[2];
		
		if (Dfs(i)){
			ans[ind] |= t;
			return true;
		}
	}
	return false;
	
}





void dfs(int u,int p = -1,int hei = 1,int ind = 0){
	// cout<<"arrived at "<<u<<" "<<hei<<endl;
	mn[u] = inf;
	h[u] = hei;
	Seen[u] = T;
	for (vector<int> v : nei[u]){
		int i = v[0];
		if (i==p)
			continue;
		if (Seen[i] == T){
			cyc[v[2]] = true;
			// cout<<"have already Seen"<<i<<" "<<h[i]<<endl;
			mn[u] = min(mn[u],h[i]);
		}
		else{
			dfs(i,u,hei+1,v[2]);
			// cout<<"returned from "<<i<<" with mn "<<mn[i]<<endl;
			mn[u] = min(mn[u],mn[i]);
		}
	}
	if (mn[u]<hei)
		cyc[ind] = true;
}

signed main(){
	int n,m;
	cin>>n>>m;
	
	for (int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		U[i] = u;
		V[i] = v;
		seen[u][v]++;
		seen[v][u]++;
		if (seen[u][v]>1)
			continue;
		nei[u].push_back({v,1,i});
		nei[v].push_back({u,2,i});
	}
	
	int p;
	cin>>p;
	while (p--){
		int u;
		cin>>u>>target;
		T++;
		Dfs(u);
	}
	
	
	
	T++;
	
	for (int i=1;i<=n;i++)
		h[i] = inf;
	
	for (int i=1;i<=n;i++)
		if (Seen[i]!=T)
			dfs(i);
	
	for (int i=1;i<=m;i++)
		if (ans[i]==3 or cyc[i] or seen[U[i]][V[i]]>1)
			cout<<"B";
		else if (ans[i]==1)
			cout<<"R";
		else
			cout<<"L";
	cout<<endl;
			
	
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 9560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 9560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 9560 KB Output isn't correct
2 Halted 0 ms 0 KB -