Submission #878649

#	Time	Username	Problem	Language	Result	Execution time	Memory
878649		Jawad_Akbar_JJ	One-Way Streets (CEOI17_oneway)	C++14	60 / 100	3037 ms	39764 KiB

oneway

#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==0 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: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40