제출 #542851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
542851		Asymmetry	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	312 KiB

oneway

//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

struct edge {
	int a, b;
};

const int N = 1001000;
int n, m, q, a, b, l;
vector<int> dp, sss, odw, gle, odp, stp, pd;
vector<edge> kr;
vector<vector<int>> v;
vector<vector<pair<int, int>>> vv;

void dfs_gle(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			gle[i] = gle[x] + 1;
			dfs_gle(i);
		}
	}
}

void dfs_dp(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			dfs_dp(i);
			dp[x] += dp[i];
		}
	}
}

void dfs_sss(int x) {
	odw[x] = l;
	for (int i : v[x]) {
		if (odw[i] < l) {
			if (dp[i] > 1) {
				sss[i] = sss[x];
			}
			dfs_sss(i);
		}
	}
}

void get(int &a) {
	a = 0;
	int g = getchar_unlocked();
	while (g < '0' || '9' < g) {
		g = getchar_unlocked();
	}
	while ('0' <= g && g <= '9') {
		a = (a << 3) + (a << 1) + g - '0';
		g = getchar_unlocked();
	}
}

int main() {
	get(n);
	get(m);
	v.resize(n + 1);
	odw.resize(n + 1);
	gle.resize(n + 1);
	sss.resize(n + 1);
	stp.resize(n + 1);
	pd.resize(n + 1);
	vv.resize(n + 1);
	kr.resize(m + 1);
	for (int i = 1; i <= m; ++i) {
		get(a);
		get(b);
		v[a].push_back(b);
		v[b].push_back(a);
		kr[i].a = a;
		kr[i].b = b;
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_gle(i);
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (gle[kr[i].a] > gle[kr[i].b]) {
			odp[i] = 1;
			swap(kr[i].a, kr[i].b);
		}
		++dp[kr[i].b];
		--dp[kr[i].a];
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_dp(i);
		}
		sss[i] = i;
	}
	++l;
	for (int i = 1; i <= n; ++i) {
		if (odw[i] < l) {
			dfs_sss(i);
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (sss[kr[i].a] == sss[kr[i].b]) {
			odp[i] = 2;
		}
		else {
			vv[sss[kr[i].a]].push_back({sss[kr[i].b], i});
			vv[sss[kr[i].b]].push_back({sss[kr[i].a], i});
			++stp[sss[kr[i].a]];
			++stp[sss[kr[i].b]];
		}
	}
	get(q);
	for (int i = 1; i <= q; ++i) {
		get(a);
		get(b);
		++pd[sss[a]];
		--pd[sss[b]];
	}
	queue<int> que;
	for (int i = 1; i <= n; ++i) {
		if (stp[i] == 1) {
			que.push(i);
		}
	}
	++l;
	while (!que.empty()) {
		int x = que.front();
		que.pop();
		odw[x] = l;
		for (auto i : vv[x]) {
			if (odw[i.first] < l) {
				--stp[i.first];
				if (pd[x] == 0) {
					odp[i.second] = 2;
				}
				else if ((pd[x] > 0) == (x == kr[i.second].b)) {
					odp[i.second] ^= 1;
				}
				pd[i.first] += pd[x];
				if (stp[i.first] == 1) {
					que.push(i.first);
				}
			}
		}
	}
	for (int i = 1; i <= m; ++i) {
		if (odp[i] == 0) {
			printf("R");
		}
		else if (odp[i] == 1) {
			printf("L");
		}
		else {
			printf("B");
		}
	}
	printf("\n");
	return 0;
}

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