oj.uz

Submission #46933

# Submission time Handle Problem Language Result Execution time Memory
46933 2018-04-25T05:42:38 Z RockyB One-Way Streets (CEOI17_oneway) C++17
100 / 100
 152 ms 51672 KB 
/// 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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Correct 6 ms 5736 KB Output is correct
3 Correct 6 ms 5816 KB Output is correct
4 Correct 7 ms 5816 KB Output is correct
5 Correct 7 ms 5936 KB Output is correct
6 Correct 7 ms 5936 KB Output is correct
7 Correct 7 ms 6024 KB Output is correct
8 Correct 9 ms 6024 KB Output is correct
9 Correct 7 ms 6024 KB Output is correct
10 Correct 7 ms 6024 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Correct 6 ms 5736 KB Output is correct
3 Correct 6 ms 5816 KB Output is correct
4 Correct 7 ms 5816 KB Output is correct
5 Correct 7 ms 5936 KB Output is correct
6 Correct 7 ms 5936 KB Output is correct
7 Correct 7 ms 6024 KB Output is correct
8 Correct 9 ms 6024 KB Output is correct
9 Correct 7 ms 6024 KB Output is correct
10 Correct 7 ms 6024 KB Output is correct
11 Correct 152 ms 12292 KB Output is correct
12 Correct 58 ms 14376 KB Output is correct
13 Correct 60 ms 16536 KB Output is correct
14 Correct 86 ms 18608 KB Output is correct
15 Correct 92 ms 20128 KB Output is correct
16 Correct 100 ms 22040 KB Output is correct
17 Correct 89 ms 24604 KB Output is correct
18 Correct 97 ms 24604 KB Output is correct
19 Correct 87 ms 28048 KB Output is correct
20 Correct 57 ms 28048 KB Output is correct
21 Correct 56 ms 28048 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5496 KB Output is correct
2 Correct 6 ms 5736 KB Output is correct
3 Correct 6 ms 5816 KB Output is correct
4 Correct 7 ms 5816 KB Output is correct
5 Correct 7 ms 5936 KB Output is correct
6 Correct 7 ms 5936 KB Output is correct
7 Correct 7 ms 6024 KB Output is correct
8 Correct 9 ms 6024 KB Output is correct
9 Correct 7 ms 6024 KB Output is correct
10 Correct 7 ms 6024 KB Output is correct
11 Correct 152 ms 12292 KB Output is correct
12 Correct 58 ms 14376 KB Output is correct
13 Correct 60 ms 16536 KB Output is correct
14 Correct 86 ms 18608 KB Output is correct
15 Correct 92 ms 20128 KB Output is correct
16 Correct 100 ms 22040 KB Output is correct
17 Correct 89 ms 24604 KB Output is correct
18 Correct 97 ms 24604 KB Output is correct
19 Correct 87 ms 28048 KB Output is correct
20 Correct 57 ms 28048 KB Output is correct
21 Correct 56 ms 28048 KB Output is correct
22 Correct 115 ms 32380 KB Output is correct
23 Correct 114 ms 33008 KB Output is correct
24 Correct 121 ms 35468 KB Output is correct
25 Correct 116 ms 42108 KB Output is correct
26 Correct 133 ms 42108 KB Output is correct
27 Correct 111 ms 42464 KB Output is correct
28 Correct 46 ms 42464 KB Output is correct
29 Correct 86 ms 42464 KB Output is correct
30 Correct 77 ms 44224 KB Output is correct
31 Correct 81 ms 46924 KB Output is correct
32 Correct 92 ms 51672 KB Output is correct