Submission #130974

#	Time	Username	Problem	Language	Result	Execution time	Memory
130974		maruii	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	263 ms	19324 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

int N, M, P;
vector<pair<pii, bool> > edge[100005];
int dfn[100005], dfnn, low[100005];
char ans[100005];
bool vis[100005];

void dfs(int x) {
	low[x] = dfn[x] = ++dfnn;
	for (auto i : edge[x]) {
		if (dfn[i.ff.ff]) {
			if (!vis[i.ff.ss]) low[x] = min(low[x], dfn[i.ff.ff]);
			vis[i.ff.ss] = 1;
			continue;
		}
		vis[i.ff.ss] = 1;
		dfs(i.ff.ff);
		low[x] = min(low[x], low[i.ff.ff]);
	}
}

int cn, cpn[100005], dep[100005], spt[17][100005];
pii par[100005];
bool dir[100005];

void dfs2(int x, int c) {
	cpn[x] = c;
	vis[x] = 1;
	for (auto i : edge[x]) {
		if (vis[i.ff.ff]) continue;
		if (low[i.ff.ff] == dfn[i.ff.ff]) {
			dep[++cn] = dep[c] + 1;
			par[cn] = pii(c, i.ff.ss);
			dir[cn] = i.ss;
			spt[0][cn] = c;
			dfs2(i.ff.ff, cn);
		}
		else dfs2(i.ff.ff, c);
	}
}

int upa[100005];
int fnd(int x) {return x == upa[x] ? x : upa[x] = fnd(upa[x]);}
void uni(int x, int y) {
	x = fnd(x), y = fnd(y);
	if (x == y) return;
	upa[y] = x;
}

int lca(int x, int y) {
	if (dep[x] < dep[y]) swap(x, y);
	for (int i = 16; i >= 0; --i) if (dep[spt[i][x]] >= dep[y]) x = spt[i][x];
	if (x == y) return x;
	for (int i = 16; i >= 0; --i) if (spt[i][x] != spt[i][y]) x = spt[i][x], y = spt[i][y];
	return spt[0][x];	
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < M; ++i) {
		int x, y; cin >> x >> y;
		edge[x].emplace_back(pii(y, i), 1);
		edge[y].emplace_back(pii(x, i), 0);
	}
	
	for (int i = 1; i <= N; ++i) if (!dfn[i]) dfs(i);
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= N; ++i) if (!vis[i]) dep[++cn] = 1, dfs2(i, cn);
	for (int i = 1; i < 17; ++i) for (int j = 1; j <= cn; ++j) spt[i][j] = spt[i-1][spt[i-1][j]];
	iota(upa, upa + cn + 1, 0);

	cin >> P;
	for (int i = 0; i < P; ++i) {
		int x, y; cin >> x >> y;
		x = cpn[x], y = cpn[y];
		int l = lca(x, y);
		for (int v = x; dep[par[fnd(v)].ff] >= dep[l]; ans[par[fnd(v)].ss] = (dir[fnd(v)] ? 'L' : 'R'), uni(par[fnd(v)].ff, v), v = fnd(v));
		for (int v = y; dep[par[fnd(v)].ff] >= dep[l]; ans[par[fnd(v)].ss] = (dir[fnd(v)] ? 'R' : 'L'), uni(par[fnd(v)].ff, v), v = fnd(v)); 
	}
	for (int i = 0; i < M; ++i) cout << ((ans[i] != 'L' && ans[i] != 'R') ? 'B' : ans[i]);
	return 0;
}

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