제출 #1325663

#제출 시각아이디문제언어결과실행 시간메모리
1325663pastaOne-Way Streets (CEOI17_oneway)C++20
0 / 100
2 ms568 KiB
//Oh? You're Approaching Me?
 
#include <bits/stdc++.h>
//#include <fstream>
using namespace std;
//  
#define int long long

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
 
 
// #pragma GCC optimize("O3,unroll-loops")
#define migmig     		    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb          		push_back
#define F           		first
#define S           		second
#define SZ(x)       		ll((x).size())
#define all(x)      		(x).begin(), (x).end()
#define cl          		clear
#define endl        		'\n'
#define deb(x)    			cerr << #x << " = " << x << '\n'
#define dokme(x)			{cout << x << endl; return;}
#define wtf					cout << "[ahaaaaaaaaaaaaaaaa]" << endl;
 
const int maxn = 2e5 + 100;
const int mod = 998244353;
const int inf = 1e18 + 5;
const int LOG = 61;
#define mid		((l + r) / 2)
#define lc		(id * 2)
#define rc		(lc + 1)
//g++ main.cpp -o main && main.exe

int n, m, q, par[maxn], h[maxn], low[maxn];
bool mark[maxn], cut[maxn];
pii E[maxn];
vector<pii> adj[maxn];
vector<pii> G[maxn];

void pre_dfs(int v, int p, int id) {
	mark[v] = 1;
	h[v] = (p == 0 ? 0 : h[p] + 1);
	low[v] = h[v];
	for (auto [u, w] : adj[v]) {
		if (!mark[u]) {
			pre_dfs(u, v, w);
			low[v] = min(low[v], low[u]);
		}
		else if (w != id) {
			low[v] = min(low[v], h[u]);
		}
	}
	if (low[v] >= h[v]) {
		cut[id] = 1;
//		deb(id);
	}
}

int get(int v) {
	if (v == par[v])
		return v;
	return par[v] = get(par[v]);
}

void merge(int v, int u) {
	v = get(v);
	u = get(u);
	if (v == u)
		return;
	par[v] = u;
}

char ans[maxn];
int ps[maxn];

void dfs(int v, int p, int id) {
	mark[v] = 1;
	for (auto [u, w] : G[v]) {
		if (u != p) {
			dfs(u, v, w);
			ps[v] += ps[u];
		}
	}
	if (ps[v] == 0) {
		ans[id] = 'B';
	}
	else if (ps[v] > 0) {
		if (v == E[id].F)
			ans[id] = 'R';
		else
			ans[id] = 'L';
	}
	else {
		if (v == E[id].F)
			ans[id] = 'L';
		else
			ans[id] = 'R';
	}
}
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int v, u;
		cin >> v >> u;
		adj[v].pb({u, i});
		adj[u].pb({v, i});
		E[i] = {v, u};
	}
	for (int i = 1; i <= n; i++)
		par[i] = i;
	pre_dfs(1, 0, 0);
	for (int i = 1; i <= m; i++) {
		if (!cut[i]) {
			merge(E[i].F, E[i].S);
		}
	}
	cin >> q;
	while (q--) {
		int v, u;
		cin >> v >> u;
		v = get(v);
		u = get(u);
		if (v == u)
			continue;
		ps[v]++;
		ps[u]--;
	}
	for (int i = 1; i <= m; i++) {
		int v = get(E[i].F), u = get(E[i].S);
		if (v == u) {
			ans[i] = 'B';
		}
		else {
			G[v].pb({u, i});
			G[u].pb({v, i});
		}
	}
	memset(mark, 0, sizeof mark);
	for (int i = 1; i <= n; i++) {
		if (!mark[i]) {
			dfs(i, 0, 0);
		}
	}
	for (int i = 1; i <= m; i++) {
		cout << ans[i];
	}
	cout << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...