Submission #526903

#	Time	Username	Problem	Language	Result	Execution time	Memory
526903		AriaH	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	355 ms	63064 KiB

oneway

/* I can do this all day */

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;

#define F first
#define S second
#define all(x) x.begin(),x.end()
#define Mp make_pair
#define point complex
#define endl '\n'
#define SZ(x) (int)x.size()
#define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout);
#define mashtali return cout << "Hello, World!", 0;

const int N = 1e5 + 10;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const double pi = acos(-1);
const ld eps = 1e-18;
const ld one = 1.;

ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; }

mt19937 rng(time(nullptr));

int n, m, H[N], mark[N], Up[N], king[N], Ans[N];

vector < pii > G[N], adj[N];

set < pii > st[N];

void dfs(int v, int last)
{
	Up[v] = H[v];
	mark[v] = 1;
	for(auto [u, id] : G[v])
	{
		///printf("v = %d last = %d u = %d id = %d\n", v, last, u, id);
		if((id ^ 1) == last) continue;
		if(mark[u])
		{
			Up[v] = min(Up[v], H[u]);
		}
		else
		{
			H[u] = H[v] + 1;
			dfs(u, id);
			Up[v] = min(Up[v], Up[u]);
		}
	}
	///printf("v = %d H = %d up = %d\n", v, H[v], Up[v]);
}

void dfs2(int v)
{
	mark[v] = 1;
	for(auto [u, id] : G[v])
	{
		if(mark[u]) continue;
		if(Up[u] > H[v])
		{
			king[u] = u;
		}
		else
		{
			king[u] = king[v];
		}
		dfs2(u);
	}
}

void solve(int v, int last)
{
	for(auto [u, id] : adj[v])
	{
		if((id ^ 1) == last) continue;
		solve(u, id);
		if(SZ(st[u]) > SZ(st[v])) st[v].swap(st[u]);
		for(auto now : st[u])
		{
			if(st[v].count({now.F ^ 1, now.S}))
			{
				st[v].erase({now.F ^ 1, now.S});
			}
			else
			{
				st[v].insert(now);
			}
		}
	}
	int side = (last & 1);
	int fir = 0;
	if(SZ(st[v]) != 0)
	{
		fir = (*st[v].begin()).F;
		Ans[last >> 1] = (1 - fir) ^ side;
	}
}

int main()
{
	fast_io;
	cin >> n >> m;
	for(int i = 1; i <= m; i ++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back({b, i << 1});
		G[b].push_back({a, i << 1 | 1});
		Ans[i] = -1;
	}
	vector < int > comp;
	for(int i = 1; i <= n; i ++)
	{
		if(!mark[i])
		{
			dfs(i, 0);
			comp.push_back(i);
		}
	}
	memset(mark, 0, sizeof mark);
	for(int i = 1; i <= n; i ++)
	{
		if(!mark[i])
		{
			king[i] = i;
			dfs2(i);
		}
	}
	for(int i = 1; i <= n; i ++)
	{
		for(auto [u, id] : G[i])
		{
			if(king[u] != king[i])
			{
				adj[king[i]].push_back(Mp(king[u], id));
			}
		}
	}
	int q;
	cin >> q;
	for(int i = 0; i < q; i ++)
	{
		int a, b;
		cin >> a >> b;
		if(king[a] == king[b])
		{
			continue;
		}
		st[king[a]].insert({0, i});
		st[king[b]].insert({1, i});
	}
	for(auto node : comp)
	{
		solve(node, 0);
	}
	for(int i = 1 ;i <= m; i ++)
	{
		if(Ans[i] == -1)
		{
			cout << "B";
		}
		else if(Ans[i] == 0)
		{
			cout << "R";
		}
		else
		{
			cout << "L";
		}
	}
	return 0;
}

/* check corner case(n = 1?), watch for negetive index or overflow */

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