Submission #761431

#	Time	Username	Problem	Language	Result	Execution time	Memory
761431		siewjh	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	135 ms	31940 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN], btadj[MAXN];
pair<int, int> pedge[MAXN];
int tvis[MAXN], lo[MAXN], comp[MAXN], p[MAXN][20], dep[MAXN], treedir[MAXN];
bool isbridge[MAXN], vis[MAXN];
int preind = 0, cmpind = -1;
void dfs(int x, int peind){
	tvis[x] = lo[x] = preind++;
	for (auto nxt : adj[x]){
		int nn = nxt.first, ne = nxt.second;
		if (ne == peind) continue;
		if (tvis[nn] != -1) lo[x] = min(lo[x], tvis[nn]);
		else{
			dfs(nn, ne);
			lo[x] = min(lo[x], lo[nn]);
			if (lo[nn] > tvis[x]) isbridge[ne] = 1;
		}
	}
}
void dfs2(int x){
	vis[x] = 1; comp[x] = cmpind;
	for (auto nxt : adj[x]){
		int nn = nxt.first, ne = nxt.second;
		if (vis[nn]) continue;
		if (isbridge[ne]) continue;
		dfs2(nn);
	}
}
void dfs3(int x, int par, int depth){
	p[x][0] = par; dep[x] = depth;
	for (auto nxt : btadj[x]){
		int nn = nxt.first, ne = nxt.second;
		if (nn == par) continue;
		pedge[nn] = {x, ne};
		dfs3(nn, x, depth + 1);
	}
}
int lca(int a, int b){
	if (dep[b] > dep[a]) swap(a, b);
	for (int k = 19; k >= 0; k--)
		if (p[a][k] != -1 && dep[p[a][k]] >= dep[b])
			a = p[a][k];
	if (a == b) return a;
	for (int k = 19; k >= 0; k--)
		if (p[a][k] != p[b][k]) {
			a = p[a][k];
			b = p[b][k];
		}
	return p[a][0];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int nodes, edges; cin >> nodes >> edges;
	vector<pair<int, int>> elist(edges);
	for (int i = 0; i < edges; i++){
		int a, b; cin >> a >> b;
		adj[a].push_back({b, i});
		adj[b].push_back({a, i});
		elist[i] = {a, b};
	}
	memset(tvis, -1, sizeof(tvis));
	for (int i = 1; i <= nodes; i++)
		if (tvis[i] == -1)
			dfs(i, -1);
	for (int i = 1; i <= nodes; i++)
		if (!vis[i]){
			cmpind++;
			dfs2(i);
		}
	for (int i = 0; i <= edges; i++)
		if (isbridge[i]){
			int a = elist[i].first, b = elist[i].second;
			a = comp[a], b = comp[b];
			btadj[a].push_back({b, i});
			btadj[b].push_back({a, i});
		}
	memset(dep, -1, sizeof(dep));
	for (int i = 0; i <= cmpind; i++)
		if (dep[i] == -1)
			dfs3(i, -1, 0);
	for (int k = 1; k <= 19; k++)
		for (int i = 0; i <= cmpind; i++){
			if (p[i][k - 1] == -1) p[i][k] = -1;
			else p[i][k] = p[p[i][k - 1]][k - 1];
		}
	int queries; cin >> queries;
	vector<tuple<int, int, int, int>> vpath(queries);
	for (int i = 0; i < queries; i++){
		int a, b, lcav; cin >> a >> b;
		a = comp[a], b = comp[b];
		lcav = lca(a, b);
		vpath[i] = make_tuple(dep[lcav], a, b, lcav);
	}
	sort(vpath.begin(), vpath.end()); // noi q5 moment
	vector<char> ans(edges, 'B');
	for (int i = 0; i < queries; i++){
		int lcad, a, b, lcav; tie(lcad, a, b, lcav) = vpath[i];
		while (a != lcav){
			int pa = pedge[a].first, pe = pedge[a].second;
			if (ans[pe] != 'B') break;
			if (comp[elist[pe].first] == a) ans[pe] = 'R';
			else ans[pe] = 'L';
			a = pa;
		}
		while (b != lcav){
			int pb = pedge[b].first, pe = pedge[b].second;
			if (ans[pe] != 'B') break;
			if (comp[elist[pe].first] == b) ans[pe] = 'L';
			else ans[pe] = 'R';
			b = pb;
		}
	}
	for (int i = 0; i < edges; i++) cout << ans[i];
}

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