Submission #118370

#	Time	Username	Problem	Language	Result	Execution time	Memory
118370		teomrn	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	283 ms	28792 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

const int NMAX = 100010;
const int LGMAX = 20;

namespace UF {
	int tata[NMAX], g[NMAX];
	
	int find(int x) {
		if (tata[tata[x]] != tata[x])
			tata[x] = find(tata[x]);
		return tata[x];
	}

	bool unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b)
			return 0;
		if (g[a] < g[b])
			swap(a, b);
		tata[b] = a, g[a] += g[b];
		return 1;
	}

	void UF(int n) {
		fill(g, g + n + 1, 1);
		iota(tata, tata + n + 1, 0);
	}
}

bool in_cicle[NMAX];
char ans[NMAX];
vector <pair <int, int>> adia[NMAX];
int muchie_tata[NMAX];
int stramos[LGMAX][NMAX];
int h[NMAX];
int lazy[LGMAX][NMAX];
// for push: 0->nimic, 1->vreau in sus, 2->vreau in jos, 4->sunt in ciclu

void dfs(int nod, int tata)
{
	stramos[0][nod] = tata;
	h[nod] = 1 + h[tata];
	for (int i = 1; i < LGMAX; i++)
		stramos[i][nod] = stramos[i - 1][stramos[i - 1][nod]];
	
	for (auto i : adia[nod]) {
		if (i.first == tata)
			muchie_tata[nod] = i.second;
		else
			dfs(i.first, nod);
	}
}

int lca(int a, int b)
{
	if (h[a] < h[b])
		swap(a, b);
	for (int i = LGMAX - 1; i >= 0; i--)
		if (h[a] - (1 << i) >= h[b])
			a = stramos[i][a];
	
	if (a == b)
		return a;

	for (int i = LGMAX - 1; i >= 0; i--)
		if (stramos[i][a] != stramos[i][b])
			a = stramos[i][a], b = stramos[i][b];

	return stramos[0][a];
}

void push_on_chain(int from, int to, int val)
{
	/// to este NEAPARAT stramos de-al lui from
	int l = h[from] - h[to];
	for (int i = LGMAX - 1; i >= 0; i--) {
		if (l >= (1 << i)) {
			lazy[i][from] |= val;
			from = stramos[i][from];
			l -= (1 << i);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, m, a, b;
	cin >> n >> m;

	UF::UF(n);

	vector <pair <int, int>> useless;

	for (int i = 1; i <= m; i++) {
		cin >> a >> b;
		if (!UF::unite(a, b)) {
			/// am un ciclu
			useless.push_back({ a, b });
			in_cicle[i] = 1;
			ans[i] = 'B';
		}
		else {
			adia[a].push_back({ b, i });
			adia[b].push_back({ a, -i });
		}
	}

	for (int i = 1; i <= n; i++)
		if (UF::find(i) == i)
			dfs(i, 0);

	for (auto i : useless) {
		int l = lca(i.first, i.second);
		push_on_chain(i.first, l, 4);
		push_on_chain(i.second, l, 4);
	}

	int q;
	cin >> q;

	while (q--) {
		cin >> a >> b;
		/// vreau sa ma duc de la a la b
		int l = lca(a, b);
		push_on_chain(a, l, 1);
		push_on_chain(b, l, 2);
	}

	for (int i = LGMAX - 1; i; i--) {
		for (int j = 1; j <= n; j++) {
			lazy[i - 1][j] |= lazy[i][j];
			lazy[i - 1][stramos[i - 1][j]] |= lazy[i][j];
		}
	}

	for (int i = 1; i <= n; i++) {
		if (muchie_tata[i] == 0)
			continue;
		bool sus = (lazy[0][i] & 1);
		bool jos = (lazy[0][i] & 2);
		int id = muchie_tata[i];
		int rev = (id < 0);
		id = abs(id);

		in_cicle[id] = (lazy[0][i] & 4);
		
		if (in_cicle[id])
			ans[id] = 'B';
		else {
			assert(!sus || !jos);
			if (sus)
				ans[id] = "RL"[rev];
			else if (jos)
				ans[id] = "LR"[rev];
			else
				ans[id] = 'B';
		}
	}

	for (int i = 1; i <= m; i++)
		cout << ans[i];

	cout << '\n';

	return 0;
}/*
5 6 
1 2 
1 2 
4 3 
2 3 
1 3 
5 1
2 
4 5 
1 3*/

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