제출 #853600

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
853600		mbfibat	One-Way Streets (CEOI17_oneway)	C++17	60 / 100	3073 ms	83108 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
const int N = 1e5 + 11;

int n, m;
char ans[N];
vector<int> adj[N];
map<ii, int> dir, org, cnt;

int height[N], lca[N][21];

int top = 0;
int cur[N], low[N];
map<ii, bool> is_bridge;

void dfs(int u, int p = 0) {
	cur[u] = low[u] = ++top;
	for (int v : adj[u]) {
		if (!cur[v]) {
			dfs(v, u);

			low[u] = min(low[u], low[v]);
//			cerr << u << ' ' << v << ' ' << low[v] << ' ' << cur[u] << '\n';
			if (low[v] > cur[u]) {
				is_bridge[ii(u, v)] = is_bridge[ii(v, u)] = (cnt[ii(u, v)] == 1);
				cerr << u << ' ' << v << ' ' << is_bridge[ii(u, v)] << '\n';				
			}
		} else if (v != p)
			low[u] = min(low[u], cur[v]);
	}
}

int id[N];
ii upd[N];
iii par[N];   
vector<iii> adj_compress[N];
void compress(int u) {
	id[u] = top;
//	cerr << u << ' ' << id[u] << '\n';
	for (int v : adj[u]) {
		if (id[v]) {
			if (id[v] != top) {
				adj_compress[id[u]].emplace_back(id[v], u, v);
				adj_compress[id[v]].emplace_back(id[u], v, u);
			}	
			continue;
		}
		if (is_bridge[ii(u, v)]) continue;

		compress(v);
	}
}

void dfs2(int u, int p = -1) {
	cur[u] = true;
	for (int j = 1; j <= 20; j++)
		lca[u][j] = lca[lca[u][j - 1]][j - 1];

	for (auto [v, x, y] : adj_compress[u]) {
		if (v == p) continue;

		height[v] = height[u] + 1;
		lca[v][0] = u;
		par[v] = iii(u, x, y);
		dfs2(v, u);
	}
}

void upd_go(int u, int v, int edge_id) {
	if (dir[ii(u, v)]) ans[edge_id] = 'R';
	else ans[edge_id] = 'L';	
}

int cal_lca(int u, int v) {
	if (height[u] > height[v]) swap(u, v);
	for (int j = 20; j >= 0; j--)
		if (height[lca[v][j]] >= height[u])
			v = lca[v][j];
	if (u == v) return u;
	for (int j = 20; j >= 0; j--)
		if (lca[u][j] != lca[v][j]) {
			u = lca[u][j];
			v = lca[v][j];
		}
	return lca[u][0];			
}

int main(int argc, char** argv) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);

		dir[ii(u, v)] = true;
		cnt[ii(u, v)]++; cnt[ii(v, u)]++;
		org[ii(u, v)] = org[ii(v, u)] = i;
	}

	for (int i = 1; i <= n; i++)
		if (!cur[i])
			dfs(i);

	cerr << "--------------------------------" << '\n';

	top = 0;
	for (int i = 1; i <= n; i++)
		if (!id[i]) {
			++top;
			compress(i);
		}	

	for (int i = 1; i <= top; i++) cur[i] = 0;
	for (int i = 1; i <= top; i++)
		if (!cur[i]) {
			height[i] = 1;
			dfs2(i);
		}						
	
	cerr << "--------------------------------" << '\n';

	for (int i = 1; i <= top; i++) upd[i] = ii(1e9, 0);
	int q; cin >> q;
	while (q--) {
		int u, v; cin >> u >> v;
		u = id[u], v = id[v];

		int p = cal_lca(u, v);

		cerr << u << ' ' << v << ' ' << p << '\n';

		upd[u] = min(upd[u], ii(height[p], 0));
		upd[v] = min(upd[v], ii(height[p], 1));
	}

	cerr << "--------------------------------" << '\n';

	vector<ii> ord;
	for (int i = 1; i <= top; i++)
		ord.emplace_back(height[i], i);
	for (int i = 1; i <= m; i++)	
		ans[i] = 'B';

	sort(ord.begin(), ord.end(), greater<ii>());

	for (auto [h, u] : ord) {
		auto [cur_h, type] = upd[u];
		auto [p, x, y] = par[u];

		if (cur_h >= h) continue;

		upd[p] = min(upd[p], upd[u]);

		int edge_id = org[ii(x, y)];

		cerr << "cur_u: " << u << ", " << x << ' ' << y << ' ' << edge_id << ' ' << type << '\n';

		if (!type) upd_go(y, x, edge_id);
		else upd_go(x, y, edge_id);
	}

	for (int i = 1; i <= m; i++)
		cout << ans[i];
}

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