답안 #45093 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
45093	2018-04-11T08:07:33 Z	qoo2p5	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	309 ms	53444 KB

oneway

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int INF = (int) 1e9 + 1e6 + 123;
const ll LINF = (ll) 1e18 + 1e9 + 123;

#define rep(i, s, t) for (auto i = (s); i < (t); ++(i))
#define per(i, s, t) for (auto i = (s); i >= (t); --(i))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back

bool mini(auto &x, const auto &y) {
	if (y < x) {
		x = y;
		return 1;
	}
	return 0;
}

bool maxi(auto &x, const auto &y) {
	if (y > x) {
		x = y;
		return 1;
	}
	return 0;
}

void run();

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	run();
	return 0;
}

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

struct E {
	int a, b;
};

int n, m;
E e[N];
vector<pair<int, int>> g[N];
bool vis[N];

int tmr;
int tin[N], fup[N];
bool is_bridge[N];

void dfs(int v, int from_id = -1) {
	tin[v] = tmr++;
	fup[v] = tin[v];
	vis[v] = 1;
	for (auto &it : g[v]) {
		if (it.second == from_id) {
			continue;
		}
		int u = it.first;
		if (vis[u]) {
			mini(fup[v], tin[u]);
		} else {
			dfs(u, it.second);
			mini(fup[v], fup[u]);
		}
	}
	
	for (auto &it : g[v]) {
		if (it.second == from_id) {
			continue;
		}
		int u = it.first;
		int id = it.second;
		if (fup[u] > tin[v]) {
			is_bridge[id] = 1;
		}
	}
}

int comps;
int which[N];
vector<pair<int, int>> adj[N];
char ans[N];

void find_comps(int v) {
	vis[v] = 1;
	which[v] = comps;
	for (auto &it : g[v]) {
		int u = it.first;
		int id = it.second;
		if (is_bridge[id]) {
			continue;
		}
		ans[id] = 'B';
		if (vis[u]) {
			continue;
		}
		find_comps(u);
	}
}

const int L = 20;
int up[N][L];
int depth[N];

void calc_lca(int v, int f = -1) {
	if (f == -1) {
		rep(i, 0, L) up[v][i] = v;
	} else {
		up[v][0] = f;
		rep(i, 1, L) up[v][i] = up[up[v][i - 1]][i - 1];
	}
	vis[v] = 1;
	for (auto &it : adj[v]) {
		int u = it.first;
		if (!vis[u]) {
			depth[u] = depth[v] + 1;
			calc_lca(u, v);
		}
	}
}

bool test(int mask, int bit) {
	return mask & (1 << bit);
}

int go(int v, int h) {
	rep(i, 0, L) if (test(h, i)) v = up[v][i];
	return v;
}

int lca(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	u = go(u, depth[u] - depth[v]);
	if (u == v) return u;
	per(i, L - 1, 0) {
		int uu = up[u][i];
		int vv = up[v][i];
		if (uu != vv) {
			u = uu, v = vv;
		}
	}
	return up[u][0];
}

int cnt_up[N], cnt_down[N];

void solve(int v, int fid = -1) {
	vis[v] = 1;
	for (auto &it : adj[v]) {
		int u = it.first;
		if (vis[u]) continue;
		solve(u, it.second);
		maxi(cnt_up[v], cnt_up[u] - 1);
		maxi(cnt_down[v], cnt_down[u] - 1);
	}
	
	assert(cnt_up[v] == 0 || cnt_down[v] == 0);
	if (fid != -1) {
		if (cnt_up[v] > 0) {
			if (which[e[fid].a] == v) {
				ans[fid] = 'R';
			} else {
				ans[fid] = 'L';
			}
		} else if (cnt_down[v] > 0) {
			if (which[e[fid].a] == v) {
				ans[fid] = 'L';
			} else {
				ans[fid] = 'R';
			}
		} else {
			ans[fid] = 'B';
		}
	}
}

void run() {
	cin >> n >> m;
	rep(i, 0, m) {
		cin >> e[i].a >> e[i].b;
		g[e[i].a].pb({e[i].b, i});
		g[e[i].b].pb({e[i].a, i});
	}
	
	rep(i, 1, n + 1) {
		if (!vis[i]) {
			dfs(i);
		}
	}
	memset(vis, 0, sizeof vis);
	rep(i, 1, n + 1) {
		if (!vis[i]) {
			find_comps(i);
			comps++;
		}
	}
	memset(vis, 0, sizeof vis);
	rep(i, 0, m) {
		int u = which[e[i].a];
		int v = which[e[i].b];
		if (u != v) {
			adj[u].pb({v, i});
			adj[v].pb({u, i});
		}
	}
	rep(i, 0, comps) {
		if (!vis[i]) {
			calc_lca(i);
		}
	}
	memset(vis, 0, sizeof vis);
	
	int p;
	cin >> p;
	while (p--) {
		int x, y;
		cin >> x >> y;
		x = which[x], y = which[y];
		if (x == y) {
			continue;
		}
		
		int w = lca(x, y);
		maxi(cnt_up[x], depth[x] - depth[w]);
		maxi(cnt_down[y], depth[y] - depth[w]);
	}
	
	rep(i, 0, comps) {
		if (!vis[i]) {
			solve(i);
		}
	}
	
	rep(i, 0, m) {
		cout << ans[i];
	}
	cout << "\n";
}

Subtask #1
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	6 ms	5348 KB	Output is correct
3	Correct	8 ms	5424 KB	Output is correct
4	Correct	6 ms	5484 KB	Output is correct
5	Correct	7 ms	5636 KB	Output is correct
6	Correct	7 ms	5636 KB	Output is correct
7	Correct	9 ms	5636 KB	Output is correct
8	Correct	8 ms	5660 KB	Output is correct
9	Correct	6 ms	5660 KB	Output is correct
10	Correct	6 ms	5660 KB	Output is correct

Subtask #2
30.0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	6 ms	5348 KB	Output is correct
3	Correct	8 ms	5424 KB	Output is correct
4	Correct	6 ms	5484 KB	Output is correct
5	Correct	7 ms	5636 KB	Output is correct
6	Correct	7 ms	5636 KB	Output is correct
7	Correct	9 ms	5636 KB	Output is correct
8	Correct	8 ms	5660 KB	Output is correct
9	Correct	6 ms	5660 KB	Output is correct
10	Correct	6 ms	5660 KB	Output is correct
11	Correct	62 ms	11708 KB	Output is correct
12	Correct	75 ms	13792 KB	Output is correct
13	Correct	72 ms	16372 KB	Output is correct
14	Correct	93 ms	20760 KB	Output is correct
15	Correct	156 ms	23184 KB	Output is correct
16	Correct	160 ms	30568 KB	Output is correct
17	Correct	166 ms	33448 KB	Output is correct
18	Correct	136 ms	33448 KB	Output is correct
19	Correct	156 ms	36928 KB	Output is correct
20	Correct	64 ms	36928 KB	Output is correct
21	Correct	70 ms	36928 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	5112 KB	Output is correct
2	Correct	6 ms	5348 KB	Output is correct
3	Correct	8 ms	5424 KB	Output is correct
4	Correct	6 ms	5484 KB	Output is correct
5	Correct	7 ms	5636 KB	Output is correct
6	Correct	7 ms	5636 KB	Output is correct
7	Correct	9 ms	5636 KB	Output is correct
8	Correct	8 ms	5660 KB	Output is correct
9	Correct	6 ms	5660 KB	Output is correct
10	Correct	6 ms	5660 KB	Output is correct
11	Correct	62 ms	11708 KB	Output is correct
12	Correct	75 ms	13792 KB	Output is correct
13	Correct	72 ms	16372 KB	Output is correct
14	Correct	93 ms	20760 KB	Output is correct
15	Correct	156 ms	23184 KB	Output is correct
16	Correct	160 ms	30568 KB	Output is correct
17	Correct	166 ms	33448 KB	Output is correct
18	Correct	136 ms	33448 KB	Output is correct
19	Correct	156 ms	36928 KB	Output is correct
20	Correct	64 ms	36928 KB	Output is correct
21	Correct	70 ms	36928 KB	Output is correct
22	Correct	283 ms	40444 KB	Output is correct
23	Correct	249 ms	41156 KB	Output is correct
24	Correct	220 ms	43772 KB	Output is correct
25	Correct	309 ms	50252 KB	Output is correct
26	Correct	245 ms	50252 KB	Output is correct
27	Correct	263 ms	50472 KB	Output is correct
28	Correct	51 ms	50472 KB	Output is correct
29	Correct	102 ms	50472 KB	Output is correct
30	Correct	105 ms	50472 KB	Output is correct
31	Correct	97 ms	50472 KB	Output is correct
32	Correct	155 ms	53444 KB	Output is correct

답안 #45093

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