Submission #445901

#	Time	Username	Problem	Language	Result	Execution time	Memory
445901		negar_a	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	234 ms	25440 KiB

oneway

#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40