Submission #1283357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283357		Jawad_Akbar_JJ	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	85 ms	21348 KiB

oneway

#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<17;
vector<pair<int,int>> nei[N];
int hei[N], par[N][20], seen[N], cyc[N], Down[N], Up[N], Ans[N];

void dfs(int u, int p){
	hei[u] = hei[p] + 1, seen[u] = 1, par[u][0] = p;
	for (int i=1;i<17;i++)
		par[u][i] = par[par[u][i-1]][i-1];

	for (auto [i, id] : nei[u]){
		if (seen[i] == 1)
			continue;
		dfs(i, u);
	}
}

void dfs2(int u, int ind){
	seen[u] = 2;
	for (auto [i, id] : nei[u]){
		if (id == -ind)
			continue;
		if (seen[i] == 2){
			
			Ans[abs(id)] = 'B';
			if (hei[i] > hei[u])
				continue;
			cyc[u]++;
			cyc[i]--;
		}
		else{
			dfs2(i, id);
			Up[u] += Up[i];
			Down[u] += Down[i];
			cyc[u] += cyc[i];
		}
	}

	if (cyc[u] or Up[u] + Down[u] == 0)
		Ans[abs(ind)] = 'B';
	else if ((Up[u] > 0) == (ind < 0))
		Ans[abs(ind)] = 'R';
	else
		Ans[abs(ind)] = 'L';
}

int Lca(int u, int v){
	if (hei[u] > hei[v])
		swap(u, v);

	for (int i=16;i>=0;i--)
		if (hei[u] + (1<<i) <= hei[v])
			v = par[v][i];

	for (int i=16;i>=0;i--)
		if (par[u][i] != par[v][i])
			u = par[u][i], v = par[v][i];

	return (u == v ? u : par[u][0]);
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, m, q;
	cin>>n>>m;

	for (int i=1, a, b;i<=m;i++){
		cin>>a>>b;
		nei[a].push_back({b, i});
		nei[b].push_back({a, -i});
	}

	for (int i=1;i<=n;i++)
		if (seen[i] == 0)
			dfs(i, 0);

	cin>>q;
	for (int i=1, A, B;i<=q;i++){
		cin>>A>>B;
		int lca = Lca(A, B);

		Up[A]++, Down[B]++, Up[lca]--, Down[lca]--;
	}
	
	for (int i=1;i<=n;i++)
		if (seen[i] != 2)
			dfs2(i, 0);

	for (int i=1;i<=m;i++)
		cout<<char(Ans[i]);
	cout<<'\n';
}

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