Submission #1130743

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130743		mmdrzada	One-Way Streets (CEOI17_oneway)	C++20	0 / 100	8 ms	10568 KiB

oneway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
 
using namespace std;

using namespace __gnu_pbds;

template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef vector<int> vi;
typedef pair<int, int> pii;
typedef long long ll;

 
#define sep ' '
#define F first
#define S second
#define fastIO   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define kill(x) {cout << x << endl;return;}
#define sz(x) int(x.size())
#define SP(x) setprecision(x) 
#define mod(x) (1ll*x%M+M)%M
#define p_q priority_queue
#define REP(i, k) for (int i = 0 ; i < k ; i ++)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int N = 1e5+10;
const int lgn = 20;
int n, m, p;

int dp_b[N], dp_p[N];
int w[N];
int h[N];
bool vis[N];
int par[N][lgn];
map<pair<int, int>, char> ans;
vi adj[N];


void dfs(int v, int p=-1) {
	vis[v] = true;
	par[v][0] = p;
	for(int i = 1 ; par[v][i-1] != -1 ; i ++) par[v][i] = par[par[v][i-1]][i-1];
	h[v] = (p == -1 ? 0 : h[p] + 1);
	
	for(int neigh: adj[v]) {
		if (!vis[neigh]) {
			dfs(neigh, v);
		}
	}
}

int lift_up(int u, int dis) {
	for(int i = 0 ; i < lgn ; i ++) {
		if ((dis>>i)&1) {
			u = par[u][i];
		}
	}
	return u;
}

int lca(int u, int v) {
	if (h[u] < h[v]) swap(u, v);
	int delta = h[u] - h[v];
	u = lift_up(u, delta);
	
	if (u == v) return u;
	
	for(int i = lgn-1 ; i >= 0 ; i --) {
		if (par[u][i] != par[v][i]) {
			u = par[u][i], v = par[v][i];
		}
	}
	return par[u][0];
}

void gfs(int v, int p = -1) {
	vis[v] = true;
	w[v] = h[v];
	
	for(int neigh: adj[v]) {
		if (!vis[neigh]) {
			gfs(neigh, v);
			dp_b[v] += dp_b[neigh];
			dp_p[v] += dp_p[neigh];
			w[v] = min(w[v], w[neigh]);
		} else if (neigh != p) w[v] = min(w[v], h[neigh]);
	}
	if (p != -1 && w[v] == h[v]) {
		assert(dp_b[v] >= 0 && dp_p[v] >= 0);
		assert(dp_b[v] == 0 || dp_p[v] == 0);
		if (dp_p[v]) {
			ans[{p, v}] = 'R';
			ans[{v, p}] = 'L';
		}
		if (dp_b[v]) {
			ans[{p, v}] = 'L';
			ans[{v, p}] = 'R';
		}
	}
}

void solve() {
	memset(par, -1, sizeof par);
	vector<pii> E;
	cin >> n >> m;
	for(int i = 0 ; i < m ; i ++) {
		int u, v; cin >> u >> v; u--, v--;
		adj[u].pb(v), adj[v].pb(u);
		E.pb({u, v});
	}
	
	for(int i = 0 ; i < n ; i ++) {
		if (!vis[i]) dfs(i);
	}
	
	cin >> p;
	for(int i = 0 ; i < p ; i ++) {
		int x, y; cin >> x >> y; x--, y--;
		int z = lca(x, y);
		assert(lift_up(x, h[x] - h[z]) == z && lift_up(y, h[y] - h[z]) == z);
		dp_b[x]++, dp_p[y]++, dp_b[z]--, dp_p[z]--;
	}
	
	fill(vis, vis+n, false);
	
	for(int i = 0 ; i < n ; i ++) {
		if (!vis[i]) gfs(i);
	}
	
	for(auto [u, v]: E) {
		if (ans.count({u, v})) {
			cout << ans[{u, v}];
		} else if (ans.count({v, u})) {
			cout << ans[{v, u}];
		} else 
			cout << 'B';
	}
	cout << endl;
}


// check MAXN
int32_t main() {
	fastIO;
	
	solve();
	
	return 0;
}

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40