Submission #1222607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222607		radodododo	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	168 ms	39916 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];
}

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

vector<int> valul;
vector<long long> val_1, val1;

long long dfs_1(long long v, long long p) {
	long long sum = val_1[v];
	used[v] = 1;
	for (auto& r : g[v]) {
		if (r.u == p) {
			continue;
		}
		sum += dfs_1(r.u, v);
	}
	if (sum > 0) {
		valul[v] = -1;
	}
	return sum;
}

long long dfs1(long long v, long long p) {
	long long sum = val1[v];
	used[v] = 1;
	for (auto& r : g[v]) {
		if (r.u == p) {
			continue;
		}
		sum += dfs1(r.u, v);
	}
	if (sum > 0) {
		valul[v] = 1;
	}
	return sum;
}


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);
	used.assign(c, 0);
	for (int i = 0; i < c; i++) {
		if (!used[i]) {
			dfs_parent(i, i);
		}
	}
	lift.resize(logg, vector<int>(c));
	countlca();
	int p;
	cin >> p;
	val_1.resize(c);
	val1.resize(c);
	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) {
			val_1[a]++;
			val_1[l]--;
		}
		if (b != l) {
			val1[b]++;
			val1[l]--;
		}
	}
	valul.resize(c);
	used.assign(c, 0);
	for (long long i = 0; i < c; i++) {
		if (!used[i]) {
			dfs_1(i, i);
		}
	}
	used.assign(c, 0);
	for (long long i = 0; i < c; i++) {
		if (!used[i]) {
			dfs1(i, i);
		}
	}
	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: 30 / 30
• Subtask 3: 40 / 40