Submission #882506

#	Time	Username	Problem	Language	Result	Execution time	Memory
882506		Alan	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	11356 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct edge {
	int v, id;
	bool inv;
};

vector<edge> g[100005], tree[100005];
int n, tin[100005], low[100005], dsu[100005], t[100005], p[100005], sz[100005], d[100005], h[100005], k;
bool bridge[100005], vis[100005];
map<pair<int, int>, int> edge;

int find (int u) {
	return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
}

void dfs (int u, int f) {
	tin[u] = low[u] = ++k;
	for (auto& [v, id, inv] : g[u]) if (v != f) {
		if (tin[v]) low[u] = min(low[u], tin[v]);
		else {
			dfs(v, u);
			low[u] = min(low[u], low[v]);
		}
		bridge[id] = tin[u] < low[v] && edge[{u, v}] == 1;
	}
}

void dfs (int u) {
	vis[u] = true;
	for (auto& [v, id, inv] : g[u]) {
		if (!bridge[id]) {
			int ru = find(u), rv = find(v);
			if (ru != rv) dsu[ru] = rv;
		}
		if (!vis[v]) dfs(v);
	}
}

void fsd (int u) {
	vis[u] = true;
	for (auto& [v, id, inv] : g[u]) {
		if (bridge[id]) {
			tree[find(u)].push_back({find(v), id, inv});
			tree[find(v)].push_back({find(u), id, !inv});
		}
		if (!vis[v]) fsd(v);
	}
}

void sdf (int u, int f) {
	p[u] = f;
	sz[u] = 1;
	if ((int) tree[u].size() > 1 && tree[u][0].v == f) swap(tree[u][0], tree[u][1]);
	for (int i = 0; i < (int) tree[u].size(); i++) if (tree[u][i].v != f) {
		d[tree[u][i].v] = d[u]+1;
		sdf(tree[u][i].v, u);
		sz[u] += sz[tree[u][i].v];
		if (sz[tree[u][i].v] > sz[tree[u][0].v]) swap(tree[u][0], tree[u][i]);
	}
}

void hld (int u, int head) {
	t[u] = ++k;
	h[u] = head;
	if (!tree[u].empty() && tree[u][0].v != p[u]) hld(tree[u][0].v, head);
	for (int i = 1; i < (int) tree[u].size(); i++) if (tree[u][i].v != p[u]) hld(tree[u][i].v, tree[u][i].v);
}

struct node {
	int sum, lz;
	node () {sum = lz = 0;}
} seg[400005];

void push (int id, int len) {
	seg[id].sum += seg[id].lz * len;
	if (id <= n*2) {
		seg[id*2].lz += seg[id].lz;
		seg[id*2+1].lz += seg[id].lz;
	}
	seg[id].lz = 0;
}

void upd (int l, int r, int id, int ql, int qr, int val) {
	push(id, r-l+1);
	if (qr < l || r < ql) return;
	if (ql <= l && r <= qr) {
		seg[id].lz += val;
		push(id, r-l+1);
		return;
	}
	upd(l, (l+r)/2, id*2, ql, qr, val);
	upd((l+r)/2+1, r, id*2+1, ql, qr, val);
}

int query (int l, int r, int id, int idx) {
	push(id, r-l+1);
	if (l == r) return seg[id].sum;
	int mid = (l+r)/2;
	if (mid < idx) return query(mid+1, r, id*2+1, idx);
	return query(l, mid, id*2, idx);
}

vector<char> ans;

void dfs_ans (int u, int f) {
	vis[u] = true;
	int q = query(1, n, 1, t[u]);
	if (q) for (auto& [v, id, inv] : tree[u]) if (v == f) ans[id] = ((q > 0) ^ inv) ? 'R' : 'L';
	for (auto& [v, id, inv] : tree[u]) if (v != f) dfs_ans(v, u);
}

int main () {
	int m;
	cin >> n >> m;
	ans.resize(m+1);
	for (int i = 1; i <= n; i++) dsu[i] = i;
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		if (u != v) {
			edge[{u, v}]++;
			edge[{v, u}]++;
			g[u].push_back({v, i+1, 0});
			g[v].push_back({u, i+1, 1});
		}
	}
	for (int i = 1; i <= n; i++) if (!tin[i]) dfs(i, 0);
	for (int i = 1; i <= n; i++) if (!vis[i]) dfs(i);
	for (int i = 1; i <= n; i++) vis[i] = false;
	for (int i = 1; i <= n; i++) if (!vis[i]) fsd(i);
	k = 0;
	for (int i = 1; i <= n; i++) if (!sz[find(i)]) sdf(find(i), 0);
	for (int i = 1; i <= n; i++) if (!t[find(i)]) hld(find(i), find(i));
	int q;
	cin >> q;
	while (q--) {
		int u, v;
		cin >> u >> v;
		u = find(u), v = find(v);
		int mul = 1;
		if (u == v) continue;
		while (h[u] != h[v]) {
			if (d[h[u]] < d[h[v]]) {
				swap(u, v);
				mul = -mul;
			}
			upd(1, n, 1, t[h[u]], t[u], mul);
			u = p[h[u]];
		}
		if (d[u] < d[v]) {
			swap(u, v);
			mul = -mul;
		}
		upd(1, n, 1, t[v]+1, t[u], mul);
	}
	for (int i = 1; i <= n; i++) vis[i] = false;
	for (int i = 1; i <= n; i++) if (!vis[find(i)]) dfs_ans(find(i), 0);
	for (int i = 1; i <= m; i++) cout << (ans[i] ? ans[i] : 'B');
	cout << '\n';
	return 0;
}

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