제출 #1222534

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1222534		radodododo	One-Way Streets (CEOI17_oneway)	C++20	30 / 100	3096 ms	22404 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;
bool used[100000];
bool doner[100000];
vector<int> topsort;
vector<int> color;
int c = 0;
vector<vector<reb>> g;
int parent[100000];
int lift[18][100000];
int logg = 18;
int h[100000];
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() {
	for (long long i = 0; i < c; i++) {
		lift[0][i] = parent[i];
	}
	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 tree[400000];

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

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

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

void up(int a, int b, int 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 (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);
	}
	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);
			}
		}
	}
	s.resize(c);
	tin.resize(c);
	tout.resize(c);
	head.resize(c);
	for (long long i = 0; i < n; i++) {
		used[i] = 0;
	}
	for (int i = 0; i < c; i++) {
		if (!used[i]) {
			dfs_parent(i, i);
			hld(i, i);
		}
	}
	countlca();
	int p;
	cin >> p;
	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);
		}
	}
	string anser;
	for (int 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]) {
			int 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 {
			int 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