oj.uz

Submission #419311

# Submission time Handle Problem Language Result Execution time Memory
419311 2021-06-06T21:54:21 Z Pbezz One-Way Streets (CEOI17_oneway) C++14
100 / 100
 393 ms 35304 KB 
#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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2800 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2800 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 183 ms 19036 KB Output is correct
12 Correct 181 ms 20308 KB Output is correct
13 Correct 188 ms 21916 KB Output is correct
14 Correct 304 ms 24624 KB Output is correct
15 Correct 257 ms 25608 KB Output is correct
16 Correct 297 ms 29676 KB Output is correct
17 Correct 284 ms 31228 KB Output is correct
18 Correct 302 ms 29700 KB Output is correct
19 Correct 287 ms 32308 KB Output is correct
20 Correct 200 ms 20536 KB Output is correct
21 Correct 157 ms 20044 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 3 ms 2800 KB Output is correct
4 Correct 3 ms 2892 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2892 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2796 KB Output is correct
11 Correct 183 ms 19036 KB Output is correct
12 Correct 181 ms 20308 KB Output is correct
13 Correct 188 ms 21916 KB Output is correct
14 Correct 304 ms 24624 KB Output is correct
15 Correct 257 ms 25608 KB Output is correct
16 Correct 297 ms 29676 KB Output is correct
17 Correct 284 ms 31228 KB Output is correct
18 Correct 302 ms 29700 KB Output is correct
19 Correct 287 ms 32308 KB Output is correct
20 Correct 200 ms 20536 KB Output is correct
21 Correct 157 ms 20044 KB Output is correct
22 Correct 344 ms 32352 KB Output is correct
23 Correct 357 ms 30752 KB Output is correct
24 Correct 393 ms 30776 KB Output is correct
25 Correct 350 ms 35304 KB Output is correct
26 Correct 339 ms 31992 KB Output is correct
27 Correct 349 ms 30872 KB Output is correct
28 Correct 122 ms 8172 KB Output is correct
29 Correct 230 ms 21228 KB Output is correct
30 Correct 264 ms 21432 KB Output is correct
31 Correct 233 ms 21700 KB Output is correct
32 Correct 267 ms 24872 KB Output is correct