Submission #1222530

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222530		radodododo	One-Way Streets (CEOI17_oneway)	C++20	30 / 100	3095 ms	22976 KiB

oneway

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define long int

using namespace std;

struct reb {
	long u, i, a, b;
	reb(long u = 0, long i = 0, long a = 0, long b = 0) {
		this->u = u;
		this->i = i;
		this->a = a;
		this->b = b;
	}
};

long n, m;
vector<vector<reb>> normg;
vector<vector<reb>> org;
vector<bool> used;
vector<bool> doner;
vector<long> topsort;
vector<long> color;
long c = 0;
vector<vector<reb>> g;
vector<long> parent;
vector<vector<long>> lift;
long logg = 18;
vector<long> h;
long high = 0;

void dfs_newg(long v) {
	topsort.push_back(v);
	used[v] = 1;
	for (auto &r : normg[v]) {
		if (!doner[r.i]) {
			doner[r.i] = 1;
			reb rr(v, r.i, r.a, r.b);
			org[r.u].push_back(rr);
		}
		if (!used[r.u]) {
			dfs_newg(r.u);
		}
	}
}

void paint(long v) {
	color[v] = c;
	for (auto &r : org[v]) {
		if (color[r.u] == -1) {
			paint(r.u);
		}
	}
}

void countlca() {
	lift[0] = parent;
	for (long k = 1; k < logg; k++) {
		for (long v = 0; v < c; v++) {
			lift[k][v] = lift[k - 1][lift[k - 1][v]];
		}
	}
}

long lca(long v, long u) {
	if (h[v] < h[u]) {
		swap(v, u);
	}
	long dist = h[v] - h[u];
	for (long k = 0; k < logg; k++) {
		if ((dist & (1 << k)) != 0) {
			v = lift[k][v];
		}
	}
	for (long k = logg - 1; k >= 0; k--) {
		if (lift[k][v] != lift[k][u]) {
			u = lift[k][u];
			v = lift[k][v];
		}
	}
	if (u == v) {
		return u;
	}
	return parent[u];
}

vector<long> s, tin, tout;
vector<long> head;
long timee = 0;

void dfs_parent(long v, long p) {
	used[v] = 1;
	parent[v] = p;
	s[v] = 1;
	h[v] = high;
	high++;
	for (auto& r : g[v]) {
		if (r.u == p) {
			continue;
		}
		dfs_parent(r.u, v);
		s[v] += s[r.u];
		if (s[g[v][0].u] < s[r.u]) {
			swap(g[v][0], r);
		}
	}
	high--;
}

void hld(long v, long p) {
	tin[v] = timee++;
	for (auto &r : g[v]) {
		if (r.u == p) {
			continue;
		}
		if (g[v][0].u == r.u) {
			head[r.u] = head[v];
		}
		else {
			head[r.u] = r.u;
		}
		hld(r.u, v);
	}
	tout[v] = timee;
}

vector<long> tree;

void sett(long i, long l, long r, long ql, long qr, long qx) {
	if (l == r) {
		return;
	}
	if (r <= ql || qr <= l) {
		return;
	}
	if (ql <= l && r <= qr) {
		tree[i] = qx;
		return;
	}
	long mid = (l + r) / 2;
	sett(2 * i + 1, l, mid, ql, qr, qx);
	sett(2 * i + 2, mid, r, ql, qr, qx);
}

long gett(long i, long l, long r, long qi) {
	if (l + 1 == r) {
		return tree[i];
	}
	if (tree[i] != 0) {
		return tree[i];
	}
	long mid = (l + r) / 2;
	if (qi < mid) {
		return gett(2 * i + 1, l, mid, qi);
	}
	return gett(2 * i + 2, mid, r, qi);
}

long pred(long a, long b) {
	return tin[a] <= tin[b] && tin[b] <= tout[a];
}

void up(long a, long b, long qx) {
	while (!pred(head[a], b)) {
		sett(0, 0, c, tin[head[a]], tin[a] + 1, qx);
		a = parent[head[a]];
	}
	sett(0, 0, c, tin[b] + 1, tin[a] + 1, qx);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	normg.resize(n);
	vector<reb> allrebs(m);
	for (long i = 0; i < m; i++) {
		long a, b;
		cin >> a >> b;
		a--, b--;
		reb ab(b, i, a, b);
		allrebs[i] = ab;
		reb ba(a, i, a, b);
		normg[a].push_back(ab);
		normg[b].push_back(ba);
	}
	used.resize(n);
	doner.resize(m);
	org.resize(n);
	for (long i = 0; i < n; i++) {
		if (!used[i]) {
			dfs_newg(i);
		}
	}
	color.resize(n, -1);
	for (auto &v : topsort) {
		if (color[v] == -1) {
			paint(v);
			c++;
		}
	}
	g.resize(c);
	for (long i = 0; i < n; i++) {
		for (auto &r : normg[i]) {
			if (color[r.a] != color[r.b]) {
				reb rrr(color[r.u], r.i, r.a, r.b);
				g[color[i]].push_back(rrr);
			}
		}
	}
	parent.resize(c);
	h.resize(c);
	s.resize(c);
	tin.resize(c);
	tout.resize(c);
	head.resize(c);
	used.assign(c, 0);
	for (long i = 0; i < c; i++) {
		if (!used[i]) {
			dfs_parent(i, i);
			hld(i, i);
		}
	}
	lift.resize(logg, vector<long>(c));
	countlca();
	tree.resize(4 * n);
	long p;
	cin >> p;
	for (long gh = 0; gh < p; gh++) {
		long a, b;
		cin >> a >> b;
		a--, b--;
		a = color[a];
		b = color[b];
		if (a == b) {
			continue;
		}
		long l = lca(a, b);
		if (a != l) {
			up(a, l, -1);
		}
		if (b != l) {
			up(b, l, 1);
		}
	}
	string anser;
	for (long i = 0; i < m; i++) {
		if (color[allrebs[i].a] == color[allrebs[i].b]) {
			anser.push_back('B');
			continue;
		}
		reb r = allrebs[i];
		r.a = color[r.a];
		r.b = color[r.b];
		if (h[r.a] > h[r.b]) {
			long val = gett(0, 0, c, tin[r.a]);
			if (val == -1) {
				anser.push_back('R');
			}
			else if (val == 1) {
				anser.push_back('L');
			}
			else {
				anser.push_back('B');
			}
		}
		else {
			long val = gett(0, 0, c, tin[r.b]);
			if (val == 1) {
				anser.push_back('R');
			}
			else if (val == -1) {
				anser.push_back('L');
			}
			else {
				anser.push_back('B');
			}
		}
	}
	cout << anser;
}

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