oj.uz

Submission #260745

# Submission time Handle Problem Language Result Execution time Memory
260745 2020-08-10T20:13:52 Z test2 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3000 ms 2688 KB 
#include<bits/stdc++.h>

#define I inline void

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 1e5 + 7 ; 

int n , m; 
string ans ; 
std::vector<pair<int , int > > adj[N];
int tim[N] ;
int t , tmr ; 
int fat[N] , par[N] , fate[N] ; 
int st[N] , en[N] , a[N] ; 
int up[N][18] ; 

int fin(int x){
	return fat[x] =  (x == fat[x] ? x : fin(fat[x])) ; 
}

I link(int u , int v){
	int uu = fin(u) ; 
	int vv = fin(v) ; 
	if(uu != vv){
		fat[uu] = vv ;
	}
}

I rec(int u , int v , int mask){

	if(tim[u] < tim[v])swap(u , v) ; 

	while(u != v){
		if(!a[fate[u]])
			a[fate[u]] = mask ;
		u = up[u][0] ; 

	}
}

bool upper(int u , int v){
	return st[v] >= st[u] && en[v] <=en[u] ; 
}

int lca(int u , int v){
	if(upper(u , v))return u ; 
	if(upper(v , u))return v ;
	for(int i = 17 ; i>= 0 ;i--){
		if(!upper(up[u][i] , v)){
			u = up[u][i];
		}
	}
	return up[u][0] ; 
}

I dfs(int x , int p ){

	tim[x] = ++ t;
	st[x] = ++ tmr ;
	up[x][0] = p ; 
	assert((x == 1 || x != p)) ; 
	for(int i = 1;i < 18 ;i++){
		up[x][i] = up[up[x][i-1]][i-1] ; 
	}
	for(auto u : adj[x]){
		if(u.first == p)continue ; 
		if(tim[u.first]){
			int l = lca(u.first , x) ; 
			rec(x , l , 3) ;
			rec(u.first , l , 3) ; 
			a[u.second] = 3 ;

		}else{
			fate[u.first] = u.second ; 
			dfs(u.first , x) ;
		}
	}
	en[x] = ++ tmr ;
}


I pre(){
	for(int i = 0 ; i < N ;i++)
		fat[i] = i ; 
}


int main(){
	ios_base::sync_with_stdio(0) ; 
	cin.tie(0) ; 
	//freopen("in.in" , "r" , stdin) ; 
	//pre() ; 
	cin >> n >> m ; 
	for(int i = 0 ;i < m ;i++){
		int u , v; 
		cin >> u >> v ; 
		if(u == v){
			a[i] = 3 ;
			continue ;
		}
		adj[u].push_back({v , i}) ; 
		adj[v].push_back({u , i }) ; 
	}
	dfs(1, 1 ) ; 

	int k ; cin >> k ;
	for(int i = 0 ;i < k ;i++){
		int u , v ;
		cin >> u >> v; 
		if(u == v)continue ; 
		int lc = lca(u , v) ;

		rec(u , lc , 1) ; 
		rec(v , lc , 2) ; 
	}

	for(int i = 0 ;i < m;i++){
		if(a[i] == 3)ans+='B' ; 
		else if(a[i] == 1)ans+='R' ;
		else if(a[i] == 2) ans+='L' ;
		else ans+='B' ;
	}

	cout<< ans ;

	return 0 ;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 2688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 2688 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3082 ms 2688 KB Time limit exceeded
2 Halted 0 ms 0 KB -