#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
// DESCRIPTION
// Given an undirected graph returns a forest
// where every node in a tree is a potential SCC in the initial graph.
// Works with multi-edges and disconnected components.
// Doesnt acctually orient the edges to make the SCC since
// The forest only considers them as nodes.
// You don't really have a connection with the previous graph.
// 0 - indexed.
// check: https://codeforces.com/contest/555/problem/E.
// Watch out for:
// 1) multi-edges.
// 2) how many components.
// 3) carefull implementation.
vector<vector<int>> Get2EdgeForest(vector<vector<pii>> &g, int n, int m, int &N, vector<int> &labels, vector<pii> &bri){
vector<int> vis(n), dep(n), is_span(m), dp(n), is_bridge(m);
vector<vector<int>> gA(n), gB(n);
vector<pii> bridges;
// finding bridges and marking them
auto dfs = [&](auto &&dfs, int u, int p, int id)->void{
vis[u] = 1;
for(auto [v, i] : g[u]) if(!vis[v]){
dep[v] = dep[u] + 1;
is_span[i] = 1;
dfs(dfs, v, u, i); // DFS AFTER DEPTH CALCULATION!!!!!!!.
}
int cnt_par = 0;
set<int> s; // UGLY with sets can be done without ' em.
for(auto [v, i] : g[u]){
if(v == p){
cnt_par += 1;
continue;
}
if(s.count(v)) continue;
s.insert(v);
if(is_span[i]) dp[u] += dp[v];
if(!is_span[i] && dep[v] > dep[u]) dp[u]--;
if(!is_span[i] && dep[v] < dep[u]) dp[u]++;
}
// cnt_par == 1 needed for multiple edges.
if(dp[u] == 0 && p != -1 && cnt_par == 1){
bridges.emplace_back(u, p);
is_bridge[id] = 1;
}
};
for(int i = 0;i < n;i++){
if(!vis[i]){
dfs(dfs, i, -1, -1);
}
}
// ceating a second graph without bridges
for(int i = 0;i < n;i++){
for(auto [j, id] : g[i]){
if(is_bridge[id]) continue;
gA[i].push_back(j);
}
}
vector<int> label(n);
fill(vis.begin(), vis.end(), false);
int cnt = 0;
// merge nodes.
auto dfs2 = [&](auto &&dfs2, int u)->void{
vis[u] = 1;
label[u] = cnt;
for(int v : gA[u]){
if(!vis[v]){
dfs2(dfs2, v);
}
}
};
for(int i = 0;i < n;i++){
if(!vis[i]){
dfs2(dfs2, i);
cnt++;
}
}
// create the tree.
for(auto [u, v] : bridges){
int orgu = u, orgv = v;
u = label[u];
v = label[v];
if(u == v) continue;
bri.emplace_back(orgu, orgv);
gB[u].push_back(v);
gB[v].push_back(u);
}
N = cnt;
labels = label;
return gB;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<vector<pair<int, int>>> g(n);
vector<pii> E(m);
string ans(m, 'B');
for(int i = 0;i < m;i++){
int a, b;
cin >> a >> b, --a, --b;
if(a == b){
ans[i] = 'B';
} else {
g[a].emplace_back(b, i);
g[b].emplace_back(a, i);
}
E[i] = make_pair(a, b);
}
int p;
cin >> p;
vector<pair<int, int>> a(p);
for(int i = 0;i < p;i++){
int x, y;
cin >> x >> y, --x, --y;
a[i] = make_pair(x, y);
}
int N;
vector<int> labels;
vector<pii> bri;
map<pii, pii> mapka;
map<pii, pii> ord;
map<pii, bool> is;
vector<vector<int>> new_g = Get2EdgeForest(g, n, m, N, labels, bri);
vector<bool> vis(N);
for(auto [x, y] : bri){
mapka[make_pair(labels[x], labels[y])] = make_pair(x, y);
is[make_pair(x, y)] = true;
}
const int LOG = 20;
vector<vector<int>> up(N, vector<int> (LOG));
vector<int> dep(N);
vector<int> L(N), A(N), B(N);
auto dfs = [&](auto &&dfs, int u, int p)->void{
vis[u] = 1;
for(int v : new_g[u]) if(v != p){
dep[v] = dep[u] + 1;
up[v][0] = u;
for(int i = 1;i < LOG;i++) up[v][i] = up[ up[v][i - 1] ][i - 1];
dfs(dfs, v, u);
}
};
auto lca = [&](int u, int v)->int{
if(dep[u] > dep[v]) swap(v, u);
int k = dep[v] - dep[u];
for(int i = LOG - 1;i >= 0;i--){
if((k >> i) & 1) v = up[v][i];
}
assert(dep[v] == dep[u]);
if(v == u) return v;
for(int i = LOG - 1;i >= 0;i--){
if(up[v][i] != up[u][i]){
u = up[u][i];
v = up[v][i];
}
}
return up[v][0];
};
for(int i = 0;i < N;i++){
if(!vis[i]){
for(int j = 0;j < LOG;j++) up[i][j] = i;
dfs(dfs, i, -1);
}
}
for(auto &[x, y] : a){ // x -> y.
x = labels[x];
y = labels[y];
int l = lca(x, y);
if(x == y) continue;
L[l]++;
A[x]++;
B[y]++;
}
auto dfs2 = [&](auto &&dfs2, int u, int p)->void{
for(int v : new_g[u]) if(v != p){
dfs2(dfs2, v, u);
A[u] += A[v];
B[u] += B[v];
}
if(p != -1){
//~ assert(not(A[u] - L[u] > 0 && B[u] - L[u] > 0));
pii real;
if(mapka.find(make_pair(u, p)) != mapka.end()){
real = mapka[make_pair(u, p)];
} else {
real = mapka[make_pair(p, u)];
}
int _a = real.first;
int _b = real.second;
if(labels[_a] != p) swap(_a, _b);
// _a is parent _b in bridge tree.
if(A[u] - L[u] > 0){
ord[real] = make_pair(_b, _a);
} else if(B[u] - L[u] > 0){
ord[real] = make_pair(_a, _b);
} else {
ord[real] = make_pair(-1, -1);
}
}
};
for(int i = 0;i < N;i++){
if(dep[i] == 0){
dfs2(dfs2, i, -1);
}
}
for(int i = 0;i < m;i++){
int _a = E[i].first;
int _b = E[i].second;
if(is[make_pair(_a, _b)]){
if(ord[make_pair(_a, _b)].first == -1) continue;
if(ord[make_pair(_a, _b)] != make_pair(_a, _b)){
ans[i] = 'L';
} else {
ans[i] = 'R';
}
} else if(is[make_pair(_b, _a)]){
swap(_a, _b);
if(ord[make_pair(_a, _b)].first == -1) continue;
if(ord[make_pair(_a, _b)] != make_pair(_a, _b)){
ans[i] = 'R';
} else {
ans[i] = 'L';
}
}
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
896 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
896 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
896 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
