/**
* author: Haunted_Cpp
**/
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif
const int MAX_N = 1e5 + 5;
const int MAX_K = 20 + 5;
map<int, int> chk_double[MAX_N];
vector<vector<int>> g(MAX_N);
vector<pair<int, int>> edge_list(MAX_N);
// Bridge Finding Procedure
vector<int> low(MAX_N), disc(MAX_N);
int Time = 0;
set<int> bridge[MAX_N];
void tarjan(int node, int p) {
low[node] = disc[node] = ++Time;
for (auto to : g[node]) {
if (to != p) {
if(!disc[to]) tarjan(to, node);
low[node] = min(low[node], low[to]);
if (chk_double[node][to] == 1 && disc[node] < low[to]) {
bridge[min(node, to)].insert(max(node, to));
}
}
}
}
bool is_bridge(int st, int et) {
if (st > et) swap(st, et);
return bridge[st].find(et) != bridge[st].end();
}
// Compress Procedure
vector<int> cor(MAX_N);
vector<vector<tuple<int, int, int>>> dag(MAX_N);
void paint(int node, int p) {
cor[node] = Time;
for (auto to : g[node]) {
if (to == p) continue;
if (is_bridge(node, to)) continue;
if (cor[to]) continue;
cor[to] = Time;
paint(to, node);
}
}
// LCA
int dp[MAX_N][MAX_K];
vector<int> H(MAX_N, -1);
void dfs(int node, int p) {
if (H[node] == -1) H[node] = 0;
dp[node][0] = p;
for (auto nxt : dag[node]) {
const int to = get<0>(nxt);
if (to == p) continue;
H[to] = H[node] + 1;
dfs(to, node);
}
}
int lca(int u, int v) {
if (H[u] < H[v]) swap(u, v);
int d = H[u] - H[v];
for (int i = 0; i < MAX_K; i++) {
if ((d >> i) & 1) {
u = dp[u][i];
}
}
if (u == v) return u;
for (int i = MAX_K - 1; ~i; i--) {
if (dp[u][i] != dp[v][i]) {
u = dp[u][i];
v = dp[v][i];
}
}
return dp[u][0];
}
// Calculate answer
bool vis[MAX_N];
vector<int> L(MAX_N), R(MAX_N);
set<pair<int, int>> dir;
int solve_l(int node, int p) {
vis[node] = true;
for (auto nxt : dag[node]) {
const int to = get<0>(nxt);
if (to == p) continue;
L[node] += solve_l(to, node);
if(L[to] > 0) {
const int st = get<1>(nxt);
const int et = get<2>(nxt);
dir.insert({et, st});
}
}
return L[node];
}
int solve_r(int node, int p) {
vis[node] = true;
for (auto nxt : dag[node]) {
const int to = get<0>(nxt);
if (to == p) continue;
R[node] += solve_r(to, node);
if(R[to] > 0) {
const int st = get<1>(nxt);
const int et = get<2>(nxt);
dir.insert({st, et});
}
}
return R[node];
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int st, et;
cin >> st >> et;
--st; --et;
edge_list[i] = {st, et};
++chk_double[st][et];
++chk_double[et][st];
g[st].emplace_back(et);
g[et].emplace_back(st);
}
// Find all bridges
for (int i = 0; i < n; i++) {
if (!disc[i]) {
tarjan(i, -1);
}
}
// Mark components and compress
Time = 0;
for (int i = 0; i < n; i++) {
if (!cor[i]) {
++Time;
paint(i, -1);
}
}
for (int st = 0; st < n; st++) {
for (auto et : g[st]) {
if (cor[st] != cor[et]) {
dag[cor[st]].emplace_back(make_tuple(cor[et], st, et));
dag[cor[et]].emplace_back(make_tuple(cor[st], et, st));
}
}
}
// LCA and start routines
memset(dp, -1, sizeof(dp));
for (int i = 1; i <= Time; i++) {
if (H[i] == -1) {
dfs(i, -1);
}
}
for (int j = 1; j < MAX_K; j++) {
for (int i = 1; i <= Time; i++) {
if (~dp[i][j - 1]) {
dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
}
}
int q;
cin >> q;
while(q--) {
int st, et;
cin >> st >> et;
--st; --et;
st = cor[st];
et = cor[et];
++L[st];
--L[lca(st, et)];
++R[et];
--R[lca(st, et)];
}
memset(vis, false, sizeof(vis));
for (int i = 1; i <= Time; i++) {
if (!vis[i]) {
solve_l(i, -1);
solve_r(i, -1);
}
}
for (int i = 0; i < m; i++) {
const int st = edge_list[i].first;
const int et = edge_list[i].second;
if (dir.find({st, et}) != dir.end()) {
cout << 'R';
continue;
}
if (dir.find({et, st}) != dir.end()) {
cout << 'L';
continue;
}
cout << 'B';
}
cout << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
27520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
27520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
27520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
