답안 #46933 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
46933	2018-04-25T05:42:38 Z	RockyB	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	152 ms	51672 KB

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.0 / 30.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #46933

Compilation message

Subtask #1 30.0 / 30.0

Subtask #2 30.0 / 30.0

Subtask #3 40.0 / 40.0

Subtask #1
30.0 / 30.0

Subtask #2
30.0 / 30.0

Subtask #3
40.0 / 40.0