oj.uz

Submission #445901

# Submission time Handle Problem Language Result Execution time Memory
445901 2021-07-20T05:55:49 Z negar_a One-Way Streets (CEOI17_oneway) C++14
100 / 100
 234 ms 25440 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define S second
#define F first
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn = 1e5 + 5, lg = 20;
vector <int> adj[maxn];
int cnt[maxn], ps1[maxn], ps2[maxn], h[maxn], com[maxn];
int par[maxn][lg + 5], x[maxn], y[maxn];
bool mark[maxn];

void dfs(int v, int cm){
	com[v] = cm;
	bool f = false;
	for(int u : adj[v]){
		if(!com[u]){
			par[u][0] = v;
			h[u] = h[v] + 1;
			for(int i = 1; i < lg; i ++){
				par[u][i] = par[par[u][i - 1]][i - 1];
			}
			dfs(u, cm);
		}
		else if(((u != par[v][0]) or (u == par[v][0] & f)) && h[u] < h[v]){
			cnt[v] ++;
			cnt[u] --;
//			cout << u << " " << v << " back_edge! " << endl;
		}
		else if(u == par[v][0]){
			f = true;
		}
	}
}
void dfs2(int v){
	mark[v] = true;
	for(int u : adj[v]){
		if(!mark[u]){
			dfs2(u);
			cnt[v] += cnt[u];
			ps1[v] += ps1[u];
			ps2[v] += ps2[u];
		}
	}	
}
int get_par(int v, int he){
	for(int i = 0; i < lg; i ++){
		if(he & (1 << i)){
			v = par[v][i];
		}
	}
	return v;
}
int lca(int u, int v){
	if(h[u] > h[v]){
		swap(u, v);
	}	
	v = get_par(v, h[v] - h[u]);
	for(int i = lg - 1; i >= 0; i --){
		if(par[v][i] != par[u][i]){
			v = par[v][i];
			u = par[u][i];
		}
	}
	if(v == u){
		return u;
	}
	return par[u][0];
}

int main(){
	fast_io;
	int n, m, q;
	cin >> n >> m;
	for(int i = 0; i < m; i ++){
		cin >> x[i] >> y[i];
		x[i] --; y[i] --;
		adj[x[i]].pb(y[i]);
		adj[y[i]].pb(x[i]);
	}	
	int c = 1;
	for(int i = 0; i < n; i ++){
		if(!com[i]){
			par[i][0] = i;
			dfs(i, c);
			c ++;
		}
	}
	cin >> q;
	bool flag = true;
	for(int i = 0; i < q; i ++){
		int s, t;
		cin >> s >> t;
		s --; t --;
		if(com[s] != com[t]){
			flag = false;
			continue;
		}
		int l = lca(s, t);
		ps1[s] ++; ps1[l] --;
		ps2[t] ++; ps2[l] --; 
	}
	for(int i = 0; i < n; i ++){
		if(!mark[i]){
			dfs2(i);
		}
	}
	for(int i = 0; i < m; i ++){
		int a = x[i], b = y[i];
		if(x[i] == y[i]){
			cout << "B";
			continue;
		}
		if(h[a] > h[b]){
			swap(a, b);
		}	
		if(cnt[b] or (!ps1[b] && !ps2[b])){
			cout << "B";
		}
		else if(ps1[b]){
			if(a == x[i]){
				cout << "L";
			}else{
				cout << "R";
			}	
		}
		else{
			if(a == x[i]){
				cout << "R";
			}else{
				cout << "L";
			}
		}
		if(!cnt[b] && ps1[b] && ps2[b]){
			assert(0);
		}
	}
	
	return 0;
}
/*
5 6
1 2
1 2
4 3
2 3
1 3
5 1
2
4 5
1 3
*/

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:31:35: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   31 |   else if(((u != par[v][0]) or (u == par[v][0] & f)) && h[u] < h[v]){
      |                                 ~~^~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:96:7: warning: variable 'flag' set but not used [-Wunused-but-set-variable]
   96 |  bool flag = true;
      |       ^~~~

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 2 ms 2800 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2812 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 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 2 ms 2800 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2812 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 48 ms 9416 KB Output is correct
12 Correct 56 ms 11700 KB Output is correct
13 Correct 78 ms 15032 KB Output is correct
14 Correct 124 ms 19092 KB Output is correct
15 Correct 114 ms 20164 KB Output is correct
16 Correct 95 ms 19676 KB Output is correct
17 Correct 99 ms 21312 KB Output is correct
18 Correct 98 ms 19684 KB Output is correct
19 Correct 102 ms 22504 KB Output is correct
20 Correct 69 ms 13752 KB Output is correct
21 Correct 63 ms 13428 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 2 ms 2800 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2892 KB Output is correct
6 Correct 2 ms 2812 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 2 ms 2764 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 48 ms 9416 KB Output is correct
12 Correct 56 ms 11700 KB Output is correct
13 Correct 78 ms 15032 KB Output is correct
14 Correct 124 ms 19092 KB Output is correct
15 Correct 114 ms 20164 KB Output is correct
16 Correct 95 ms 19676 KB Output is correct
17 Correct 99 ms 21312 KB Output is correct
18 Correct 98 ms 19684 KB Output is correct
19 Correct 102 ms 22504 KB Output is correct
20 Correct 69 ms 13752 KB Output is correct
21 Correct 63 ms 13428 KB Output is correct
22 Correct 202 ms 22440 KB Output is correct
23 Correct 169 ms 20948 KB Output is correct
24 Correct 164 ms 20836 KB Output is correct
25 Correct 234 ms 25440 KB Output is correct
26 Correct 206 ms 22016 KB Output is correct
27 Correct 194 ms 20924 KB Output is correct
28 Correct 59 ms 5776 KB Output is correct
29 Correct 133 ms 14552 KB Output is correct
30 Correct 141 ms 14608 KB Output is correct
31 Correct 162 ms 15084 KB Output is correct
32 Correct 164 ms 18524 KB Output is correct