oj.uz

Submission #655847

# Submission time Handle Problem Language Result Execution time Memory
655847 2022-11-05T19:00:41 Z manizare One-Way Streets (CEOI17_oneway) C++14
60 / 100
 2228 ms 262144 KB 
#include<bits/stdc++.h>
#define all(a) a.begin(),a.end()
#define pb push_back
using namespace std ;

const int maxn = 1e5 + 10 , maxq = 502 , inf = 1e9 , mod = 1e9+7 ;
vector <pair <int , int > > G[maxn] ;
vector <int>  l[maxn] ;
int dp[maxn] ;
bool mark2[maxn] , mark[maxn] ;int par[maxn]  , cnt = 1 ,c[maxn] , pr[maxn] , pp[maxn] , ans[maxn]; 
pair <int , int > ed[maxn] ;
void dfs(int v){ 
	mark[v] = 1;
	for(int i = 0; i < (int)G[v].size() ; i++){
		int u = G[v][i].first , id = G[v][i].second ;
		if(mark[u] == 1){
			if(mark2[id] == 0){
				dp[v] ++ ;
				dp[u] -- ;
				ans[id] = 3 ;
				mark2[id] = 1; 
			}
			continue ;
		}
		mark2[id] = 1;
		par[u] = id ;
		dfs(u) ;
		dp[v]+=dp[u];
	}
}

void dfs2(int v , int r){
	mark[v] = 1;
	c[v] = r ;
	for(int i = 0; i < (int)G[v].size() ; i++){
		int u = G[v][i].first , id = G[v][i].second ;
		if(mark[u] == 1)continue ;
		if(dp[u] == 0){
			cnt ++;
			//cout << v << " " << u << "<---\n";
			pr[cnt] = id ;
			pp[cnt] = r ;
			l[r].pb(cnt);
			dfs2(u , cnt);
		}else{
			dfs2(u , r);
		}
	}
}
vector <int> vv[maxn] , uu[maxn] ;
int sec = 1 ;
void dfs3(int v){
	mark[v] = 1;
	for(int i = 0 ;i < (int)l[v].size() ; i++){
		int u = l[v][i] ;
		dfs3(u);
	}
	if(pp[v] == 0){
		vv[v].clear();uu[v].clear(); 
		return ;
	} 
	int ok = 0 , ok1 = 0 ;
	sort(all(vv[v]));sort(all(uu[v]));
	while(vv[v].size() > 0 && uu[v].size() > 0){
		int vx = vv[v].back() , vz = uu[v].back() ;
		if(vx == vz){
			vv[v].pop_back();
			uu[v].pop_back();
		}else if(vx > vz){
			vv[pp[v]].pb(vx);
			ok += 1; 
			vv[v].pop_back();
		}else{
			ok1+=1;
			uu[pp[v]].pb(vz);
			uu[v].pop_back();
		}
	}
	while(vv[v].size() > 0){
		int vx = vv[v].back(); vv[v].pop_back();
		ok += 1 ;
		vv[pp[v]].pb(vx);
	}
	while(uu[v].size() > 0){
		int vx = uu[v].back() ; uu[v].pop_back();
		ok1 += 1;
		uu[pp[v]].pb(vx);
	}
	int id = pr[v]; 
	if(ok == 0 && ok1 ==0 ){
		ans[pr[v]] = 3 ;
	}else if (ok1 == 0){
		if(c[ed[id].first] == v){
			ans[id] = 2 ; 
		}else{
			ans[id] = 1 ;
		}
	}else{
		if(c[ed[id].first] == v){
			ans[id] = 1 ;
		}else{
			ans[id] = 2 ;
		}
	}
	uu[v].clear();
	vv[v].clear();
}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);cout.tie(0);
	int n , m ;
	cin >> n >> m ;
	for(int i =1  ;i <= m ; i++){
		int v , u ;
		cin >> v >> u ;
		if(v==u){
			ans[i] = 3; 
			continue ;
		}
		G[v].pb({u,i});
		G[u].pb({v,i});
		ed[i] = {v , u} ;
	}
	for(int i = 1; i <= n ; i++){
		if(mark[i] == 1)continue ;
		dfs(i);
	}
	for(int i =1 ; i <= n ; i++){
		if(par[i] == 0)continue ;
		if(dp[i] >= 1){
			ans[par[i]] = 3 ;
		}
	}
	memset(mark , 0 , sizeof mark);
	memset(mark2 , 0 , sizeof mark2);
	vector <int> vec ;
	for(int i =1; i <= n ; i ++){
		if(mark[i] == 1)continue ;
		vec.pb(cnt);
		dfs2(i ,cnt ) ;
		cnt++;
	}
	memset(mark , 0 , sizeof mark);

	int q ;
	cin >> q ;
	while(q--){
		int v , u ;
		cin >> v >> u ;
		if(c[v] == c[u])continue ;
		vv[c[v]].pb(q);
		uu[c[u]].pb(q);
	}
	for(int i =1 ; i <= n ; i++)G[i].clear();
	for(int i =0 ; i < (int)vec.size() ;i++){
		int u = vec[i]; 
		dfs3(u);
	}
	for(int i = 1 ; i <= m ; i++){
		if(ans[i] == 3){
			cout << "B";
		}
		if(ans[i] == 2){
			cout << "R";
		}
		if(ans[i] == 1){
			cout << "L" ;
		}
	}
	cout << endl;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 6 ms 10196 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 6 ms 10196 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 44 ms 15308 KB Output is correct
12 Correct 45 ms 16204 KB Output is correct
13 Correct 49 ms 17304 KB Output is correct
14 Correct 57 ms 18140 KB Output is correct
15 Correct 63 ms 18480 KB Output is correct
16 Correct 65 ms 18416 KB Output is correct
17 Correct 95 ms 33048 KB Output is correct
18 Correct 71 ms 18424 KB Output is correct
19 Correct 91 ms 34944 KB Output is correct
20 Correct 45 ms 15740 KB Output is correct
21 Correct 41 ms 15716 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9940 KB Output is correct
2 Correct 5 ms 9940 KB Output is correct
3 Correct 5 ms 9940 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 6 ms 10196 KB Output is correct
6 Correct 5 ms 9940 KB Output is correct
7 Correct 6 ms 10196 KB Output is correct
8 Correct 6 ms 9940 KB Output is correct
9 Correct 5 ms 9940 KB Output is correct
10 Correct 5 ms 9940 KB Output is correct
11 Correct 44 ms 15308 KB Output is correct
12 Correct 45 ms 16204 KB Output is correct
13 Correct 49 ms 17304 KB Output is correct
14 Correct 57 ms 18140 KB Output is correct
15 Correct 63 ms 18480 KB Output is correct
16 Correct 65 ms 18416 KB Output is correct
17 Correct 95 ms 33048 KB Output is correct
18 Correct 71 ms 18424 KB Output is correct
19 Correct 91 ms 34944 KB Output is correct
20 Correct 45 ms 15740 KB Output is correct
21 Correct 41 ms 15716 KB Output is correct
22 Runtime error 2228 ms 262144 KB Execution killed with signal 9
23 Halted 0 ms 0 KB -