제출 #546748

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

oneway

#include <bits/stdc++.h>
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
using namespace std;
using PII = pair <int, int>;

struct Edge {
	int a, b, id;
	bool operator < (const Edge& x) const {
		return mp(a, b) < mp(x.a, x.b);
	}
};
const int N = 1e5+5;
vector <PII> paths[N];
vector <Edge> edges;
int n, m, k, q, curT;
int vis[N], dp[N];
int par[N];
int find(int a) {
	if (par[a] == a) return a;
	return par[a] = find(par[a]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	par[b] = a;
}
stack <int> stk;
int dfs(int pos, int p = -1) {
	vis[pos] = ++curT;
	// cout << pos << '\n';
	int got = 0;
	for (auto& [a, b] : paths[pos]) {
		if (b == p || vis[a] > vis[pos]) continue;
		if (vis[a] > 0 && vis[a] < vis[pos]) {
			dp[pos]++;
			dp[a]--;
			continue;
		}
		got += dfs(a, b);
	}
	// cout << "VAL: " << pos << ' ' << dp[pos]+got << '\n';
	if (dp[pos]+got > 0) stk.push(pos);
	if (!stk.empty() && got > 0 && got+dp[pos]==0) {
		int cur = pos;
		while(!stk.empty()) {
			int x = stk.top(); stk.pop();
			merge(cur, x);
		}
	}
	dp[pos] += got;
	return dp[pos];
}
string answ = "XLRB";
int ans[N]; // 1 L, 2 R, 3 B
map <PII, int> ids;
bool vis1[N];
int dfs1(int pos, int par = 0) {
	if (vis1[pos]) return 0;
	vis1[pos] = 1;
	// cout << pos << ' ' << par << '\n';
	for (auto& [a, b] : paths[pos]) {
		if (a == par) continue;
		if (find(a) == find(pos)) dfs1(a, pos);
		else dp[pos] += dfs1(a, pos);
	}
	if (par > 0) {
		// cout << pos << ' ' << par << '\n';
		if (dp[pos] > 0) {
			ans[ids[{pos, par}]] |= 2;
		} else if (dp[pos] == 0) {
			ans[ids[{pos, par}]] |= 3;
		} else {
			ans[ids[{pos, par}]] |= 1;
		}
	}
	return dp[pos];
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int a, b; cin >> a >> b;

		if (a > b) swap(a, b);
		if (a == b) {
			ans[i] |= 3;
		} else {
			edges.pb({a, b, i});
			paths[a].pb({b, i});
			paths[b].pb({a, i});
		}
		ids[{a, b}] = i;
		ids[{b, a}] = i;
	}
	// find and merge cycles
	{
		iota(par+1, par+1+n, 1);
		dfs(1);
		
		// for (int i = 1; i <= n; i++) {
		// 	cout << i << ": " << find(i) << '\n';
		// }
	}
	memset(dp, 0, sizeof(dp));
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int a, b; cin >> a >> b;
		dp[a]++; dp[b]--;
	}
	for (int i = 1; i <= n; i++) {
		int x = find(i);
		if (x == i) continue;
		for (auto el : paths[i]) paths[x].pb(el);
	}
	
	dfs1(find(1));
	for (auto edge : edges) {
		if (find(edge.a) == find(edge.b)) ans[edge.id] |= 3;
	}
	for (int i = 1; i <= m; i++) cout << answ[ans[i]];
		cout << '\n';
}

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