oj.uz

Submission #260761

# Submission time Handle Problem Language Result Execution time Memory
260761 2020-08-10T21:04:58 Z test2 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 3 ms 3328 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] , dir[N] ; 
int up[N][18] ; 

int cols[N] , col ; 

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

int fin(int x){
	if(x == fat[x])return x ; 
	return fat[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) ; 
	u = fin(u) ; 
	while(upper(v , u) && u != v){
		if(!a[fate[u]]){
			if(mask  == 1){
				a[fate[u]] = (dir[fate[u]] == u ? 1 : 2 ) ; 
			}else if(mask == 2){
				a[fate[u]] = (dir[fate[u]] == u ? 2 : 1) ; 
			}
			else{
				a[fate[u]] = mask ;
			}
		}
		link(u , up[u][0]) ; 
		u = fin(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 ; 

	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 , u.first , 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 ; 
		dir[i] = v ; 
		if(u == v){
			a[i] = 3 ;
			continue ;
		}
		adj[u].push_back({v , i}) ; 
		adj[v].push_back({u , i }) ; 
	}
	for(int i = 1; i<=n;i++)
		if(!tim[i])
			dfs(i, i ) ; 

		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] == 2)ans+='R' ;
			else if(a[i] == 1) ans+='L' ;
			else ans+='B' ;
		}

		cout<< ans ;

		return 0 ;
	}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:84:8: warning: unused variable 'l' [-Wunused-variable]
    int l = lca(u.first , x) ; 
        ^
oneway.cpp: In function 'int main()':
oneway.cpp:120:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i = 1; i<=n;i++)
  ^~~
oneway.cpp:124:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   int k ; cin >> k ;
   ^~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 2 ms 3200 KB Output is correct
4 Correct 3 ms 3200 KB Output is correct
5 Correct 3 ms 3200 KB Output is correct
6 Correct 2 ms 3200 KB Output is correct
7 Correct 3 ms 3328 KB Output is correct
8 Correct 3 ms 3200 KB Output is correct
9 Incorrect 2 ms 3200 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 2 ms 3200 KB Output is correct
4 Correct 3 ms 3200 KB Output is correct
5 Correct 3 ms 3200 KB Output is correct
6 Correct 2 ms 3200 KB Output is correct
7 Correct 3 ms 3328 KB Output is correct
8 Correct 3 ms 3200 KB Output is correct
9 Incorrect 2 ms 3200 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3072 KB Output is correct
2 Correct 2 ms 3072 KB Output is correct
3 Correct 2 ms 3200 KB Output is correct
4 Correct 3 ms 3200 KB Output is correct
5 Correct 3 ms 3200 KB Output is correct
6 Correct 2 ms 3200 KB Output is correct
7 Correct 3 ms 3328 KB Output is correct
8 Correct 3 ms 3200 KB Output is correct
9 Incorrect 2 ms 3200 KB Output isn't correct
10 Halted 0 ms 0 KB -