Submission #1222581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222581		radodododo	One-Way Streets (CEOI17_oneway)	C++17	30 / 100	3096 ms	22720 KiB

oneway

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

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

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

void dfs_newg(int 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(int v) {
	color[v] = c;
	for (auto& r : org[v]) {
		if (color[r.u] == -1) {
			paint(r.u);
		}
	}
}

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

int lca(int v, int u) {
	if (h[v] < h[u]) {
		swap(v, u);
	}
	int dist = h[v] - h[u];
	for (int k = 0; k < logg; k++) {
		if ((dist & (1 << k)) != 0) {
			v = lift[k][v];
		}
	}
	for (int 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<int> s, tin, tout;
vector<int> head;
int timee = 0;

void dfs_parent(int v, int 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(int v, int 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;
}

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

vector<long long> begin_1, begin1, end_1, end1;

void up(int a, int b, int qx) {
	while (!pred(head[a], b)) {
		if (qx == -1) {
			begin_1[tin[head[a]]]++;
			end_1[tin[a] + 1]++;
		}
		else {
			begin1[tin[head[a]]]++;
			end1[tin[a] + 1]++;
		}
		a = parent[head[a]];
	}
	if (qx == -1) {
		begin_1[tin[b] + 1]++;
		end_1[tin[a] + 1]++;
	}
	else {
		begin1[tin[b] + 1]++;
		end1[tin[a] + 1]++;
	}
}

vector<int> valul;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	normg.resize(n);
	vector<reb> allrebs(m);
	for (int i = 0; i < m; i++) {
		int 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 (int 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 (int 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 (int i = 0; i < c; i++) {
		if (!used[i]) {
			dfs_parent(i, i);
			hld(i, i);
		}
	}
	lift.resize(logg, vector<int>(c));
	countlca();
	int p;
	cin >> p;
	begin_1.resize(c + 1);
	begin1.resize(c + 1);
	end_1.resize(c + 1);
	end1.resize(c + 1);
	for (int gh = 0; gh < p; gh++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		a = color[a];
		b = color[b];
		if (a == b) {
			continue;
		}
		int l = lca(a, b);
		if (a != l) {
			up(a, l, -1);
		}
		if (b != l) {
			up(b, l, 1);
		}
	}
	valul.resize(c);
	vector<int> orderer(c);
	for (int i = 0; i < c; i++) {
		orderer[tin[i]] = i;
	}
	int much_1 = 0;
	int much1 = 0;
	for (int i = 0; i < c; i++) {
		much_1 += begin_1[i] - end_1[i];
		much1 += begin1[i] - end1[i];
		if (much_1 > 0) {
			valul[orderer[i]] = -1;
		} else if (much1 > 0) {
			valul[orderer[i]] = 1;
		}
	}
	for (int i = 0; i < m; i++) {
		if (color[allrebs[i].a] == color[allrebs[i].b]) {
			cout << 'B';
			continue;
		}
		reb r = allrebs[i];
		r.a = color[r.a];
		r.b = color[r.b];
		if (h[r.a] > h[r.b]) {
			int val = valul[r.a];
			if (val == -1) {
				cout << 'R';
			}
			else if (val == 1) {
				cout << 'L';
			}
			else {
				cout << 'B';
			}
		}
		else {
			int val = valul[r.b];
			if (val == 1) {
				cout << 'R';
			}
			else if (val == -1) {
				cout << 'L';
			}
			else {
				cout << 'B';
			}
		}
	}
}

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