Submission #46933

#	Time	Username	Problem	Language	Result	Execution time	Memory
46933		RockyB	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	152 ms	51672 KiB

oneway

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

const int N = (int)1e5 + 7;

using namespace std;

int n, m, k;
pair <int, int> a[N], b[N];
char ans[N];
vector < pair <int, int> > g[N], g1[N];

int tmr, cnt;
vector <int> cur;
int dp[N], tin[N], id[N];
bool was[N], br[N];

void dfs(int v, int p = -1) {
	was[v] = 1;
	dp[v] = tin[v] = ++tmr;
	for (auto to : g[v]) {
		if (to.s == p) continue;
		if (was[to.f]) dp[v] = min(dp[v], tin[to.f]);
		else {
			int fix = sz(cur);
			dfs(to.f, to.s);
			dp[v] = min(dp[v], dp[to.f]);
			if (tin[v] < dp[to.f]) {
				br[to.s] = 1;
				++cnt;
				while (sz(cur) != fix) {
					id[cur.back()] = cnt;
					cur.pp();
				}
			}
		}
	}
	cur.pb(v);
}
void dfs1(int v, int p) {
	was[v] = 1;
	for (auto to : g1[v]) {
		if (to.s == p) continue;
		if (was[to.f]) assert(0);
		dfs1(to.f, to.s);
		dp[v] += dp[to.f];
		if (!dp[to.f]) {
			ans[to.s] = 'B';
		} else if (dp[to.f] > 0) ans[to.s] = (id[a[to.s].f] == v) ? 'L' : 'R';
		else ans[to.s] = (id[a[to.s].f] == v) ? 'R' : 'L';
	}
}

int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> m;
	rep(i, 1, m) {
		cin >> a[i].f >> a[i].s;
		g[a[i].f].pb({a[i].s, i});
		g[a[i].s].pb({a[i].f, i});
	}
	cin >> k;
	rep(i, 1, k) {
		cin >> b[i].f >> b[i].s;
	}
	rep(i, 1, n) {
		if (!was[i]) {
			dfs(i);
			++cnt;
			while (sz(cur)) {
				id[cur.back()] = cnt;
				cur.pp();
			}
		}
	}
	rep(i, 1, m) {
		if (!br[i]) {
			ans[i] = 'B';
		} else {
			g1[id[a[i].f]].pb({id[a[i].s], i});
			g1[id[a[i].s]].pb({id[a[i].f], i});
		}
	}
	memset(dp, 0, sizeof(dp));
	rep(i, 1, k) {
		dp[id[b[i].f]]++, dp[id[b[i].s]]--;
	}
	memset(was, 0, sizeof(was));
	rep(i, 1, cnt) {
		if (!was[i]) dfs1(i, -1);
	}
	rep(i, 1, m) {
		cout << ans[i];
	}
	ioi
}

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