Submission #1301818

#TimeUsernameProblemLanguageResultExecution timeMemory
1301818witek_cppOne-Way Streets (CEOI17_oneway)C++20
0 / 100
0 ms332 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;
typedef long long ll;

#define st first
#define nd second
#define f(a, c, b) for (int a = c; b > a; a++)
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define int ll
#define DUZO 1000000000000000000
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;

vector<pii> kr;
set<pii> musi;
set<pii> kr_musi;
vvi g;
vi dp;
vi pre;
vvi nie_mosty;
vector<pii> mosty;
vi na_cyklu;
vi odw;
vvi g_dw;
vi nr_dw;
int lnk = 1;
int t;

int nowy(int v, int ind) {
	if (kr[ind].st != v) return kr[ind].st;
	else return kr[ind].nd;
}

void dfs(int v, int p) {
	pre[v] = dp[v] = t;
	odw[v] = 1;
	t++;
	for (int ind: g[v]) {
		if (ind == p) continue;
		int u = nowy(v, ind);
		if (!odw[u]) {
			dfs(u, ind);
			dp[v] = min(dp[v], dp[u]);
		} else {
			dp[v] = min(dp[v], pre[u]);
		}
		if (pre[v] < pre[u]) {
			if (dp[u] <= pre[v]) {
				nie_mosty[u].pb(ind);
				nie_mosty[v].pb(ind);
			} else {
				mosty.pb({u, v});
			}
		}
	}
}

void dfs_nm(int v) {
	nr_dw[v] = lnk;
	for (int ind: nie_mosty[v]) {
		int u = nowy(v, ind);
		if (nr_dw[u]) continue;
		dfs_nm(u);
	}
}

void dfs_dw(int v, int p) {
	for (int u: g_dw[v]) {
		if (u == p) continue;
		dfs_dw(u, v);
		if (dp[u] > 0) {
			musi.insert({u, v});
		} else if (dp[u] < 0) {
			musi.insert({v, u});
		}
		dp[v] += dp[u];
	}
}

void solve() {
	int n, m;
	cin >> n >> m;
	kr.resize(m);
	g.resize(n + 1);
	f(i, 0, m) {
		int u, v;
		cin >> u >> v;
		kr[i] = {u, v};
		g[u].pb(i);
		g[v].pb(i);	
	}
	pre.resize(n + 1);
	t = 0;
	dp.resize(n + 1);
	odw.resize(n + 1);
	nie_mosty = {};
	nie_mosty.resize(n + 1);
	dfs(1, -1);
	nr_dw.resize(n + 1, 0);
	f(i, 1, n + 1) {
		if (nr_dw[i]) continue;
		dfs_nm(i);
		lnk++;
	}
	g_dw.resize(lnk);
	for (auto [c, d]: mosty) {
		int u = nr_dw[c];
		int v = nr_dw[d];
		g_dw[u].pb(v);
		g_dw[v].pb(u);
	}
	f(i, 1, lnk) {
		dp[i] = 0;
	}
	int q;
	cin >> q;
	f(i, 0, q) {
		int u, v;
		cin >> u >> v;
		u = nr_dw[u];
		v = nr_dw[v];
		dp[u]++;
		dp[v]--;
	}
	/*cout << "a\n";
	f(i, 1, sz(g_dw)) {
		cout << "wierzcholek " << i << " sasiedzi to: ";
		for (int ele: g_dw[i]) {
			cout << ele << " ";
		}
		cout << "\n";
	}*/
	dfs_dw(1, 0);
	/*for (pii ele: musi) {
		cout << ele.st << " " << ele.nd << "\n";
	}*/
	for (auto [c, d]: mosty) {
		int u = nr_dw[c];
		int v = nr_dw[d];
		if (musi.count({v, u})) {
			kr_musi.insert({d, c});
		} else if (musi.count({u, v})) {
			kr_musi.insert({c, d});
		}
	}
	for (auto [u, v]: kr) {
		if (kr_musi.count({u, v})) {
			cout<< "R";
		} else if (kr_musi.count({v, u})) {
			cout << "L";
		} else {
			cout << "B";
		}
	}
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int q = 1;
    //cin >> q;
    while (q--) solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...