Submission #419311

#	Time	Username	Problem	Language	Result	Execution time	Memory
419311		Pbezz	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	393 ms	35304 KiB

oneway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long
#define pb push_back
typedef pair<ll,ll> pii;

typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

const ll MAXN=1e5+5;
const ll INF= 1e9+10;

vector<vector<ll>>adj(MAXN);
ll dp[MAXN], lvl[MAXN], pr[MAXN], balance[MAXN];
bool bridge[MAXN];

map<pii,vector<ll>>mapi;

ll st=1;
void dfs(ll node){
dp[node]=-1;

for(auto u:adj[node]){

if(lvl[u]==0){//tree edge
lvl[u]=lvl[node]+1;
pr[u]=node;
dfs(u);

balance[node]+=balance[u];
dp[node]+=dp[u];
}else if(lvl[u]>lvl[node]){
dp[node]--;
}else if(lvl[u]<lvl[node]){
dp[node]++;
}

}

if(node==st)return;

if(dp[node]==0){//bridge
bridge[node]=true;
}

}

int main(){

	ll n,m,p,i,a,b;
	cin>>n>>m;
	vector<char>ans(m);
	for(i=0;i<m;i++){ans[i]='B';

	cin>>a>>b;
	//if(a>b)swap(a,b);
	mapi[{a,b}].pb(i);

	adj[a].pb(b);
	adj[b].pb(a);
}

	cin>>p;
	while(p--){
	cin>>a>>b;

	balance[a]++;
	balance[b]--;
}

	for(i=1;i<=n;i++){ 

	if(lvl[i]==0){
	st=i;
	lvl[i]=1;
	dfs(i);
	}

	}


	for(i=1;i<=n;i++){

	//cout<<i<<" "<<dp[i]<<" "<<balance[i]<<'\n';
	if(bridge[i]==false)continue;
	a = pr[i]; b=i; 
	if(balance[i]>0){

	//iterar por mapi[edge] e mapi[-edge]
	for(auto u:mapi[{a,b}]){
	ans[u]='L';
	}
	for(auto u:mapi[{b,a}]){
	ans[u]='R';
	}

	}else if(balance[i]<0){

	for(auto u:mapi[{a,b}]){
	ans[u]='R';
	}
	for(auto u:mapi[{b,a}]){
	ans[u]='L';
	}

	}else{

	for(auto u:mapi[{a,b}]){
	ans[u]='B';
	}
	for(auto u:mapi[{b,a}]){
	ans[u]='B';
	}

	}


}

	for(i=0;i<m;i++){
	cout<<ans[i];
	}cout<<'\n';


return 0;
}

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