#include <bits/stdc++.h>
using namespace std;
const int k_N = 1e5 + 3;
struct DisjointSetUnion{
int p[k_N], sz[k_N];
DisjointSetUnion(){}
void resize(int n){
for(int i = 1; i <= n; ++i){
p[i] = i;
sz[i] = 1;
}
}
int get_p(int x){
if(p[x] == x) return x;
return p[x] = get_p(p[x]);
}
bool unite(int u, int v){
if(get_p(u) == get_p(v))
return false;
if(sz[p[u]] < sz[p[v]])
swap(u, v);
sz[p[u]] += sz[p[v]];
p[p[v]] = p[u];
return true;
}
};
int n, m, p;
vector<pair<int, int>> adjacent[k_N];
pair<int, int> edges[k_N];
bool used[k_N];
int depth[k_N];
char ans[k_N];
DisjointSetUnion dsu;
vector<int> adj_dsu[k_N], adj2[k_N];
vector<pair<int, bool>> ve[k_N];
int lca[20][k_N], lca_par[k_N];
void dfs_lca(int node){
for(int to: adj2[node]){
if(to == lca_par[node])
continue;
lca_par[to] = node;
depth[to] = depth[node] + 1;
dfs_lca(to);
}
}
void init_lca(){
for(int i = 1; i <= n; ++i) used[i] = false;
for(int i = 1; i <= n; ++i){
int x = dsu.get_p(i);
if(!used[x]){
depth[x] = 0;
lca_par[x] = dsu.get_p(x);
dfs_lca(x);
}
}
for(int j = 1; j <= n; ++j)
lca[0][j] = lca_par[j];
for(int i = 1; i < 20; ++i)
for(int j = 1; j <= n; ++j)
lca[i][j] = lca[i - 1][lca[i - 1][j]];
}
int get_lca(int u, int v){
if(depth[u] < depth[v])
swap(u, v);
int diff = depth[u] - depth[v];
for(int i = 19; i >= 0; --i)
if(diff & (1 << i))
u = lca[i][u];
if(u == v) return u;
for(int i = 19; i >= 0; --i){
if(lca[i][u] != lca[i][v]){
u = lca[i][u];
v = lca[i][v];
}
}
return lca[0][u];
}
int cycle(int node, int p_idx){
used[node] = true;
int ret = node;
for(auto [to, idx]: adjacent[node]){
if(idx == p_idx)
continue;
if(used[to]){
ans[idx] = 'B';
if(depth[to] < depth[ret]) ret = to;
}
else{
depth[to] = depth[node] + 1;
int x = cycle(to, idx);
if(x != to) ans[idx] = 'B';
if(depth[x] < depth[ret]) ret = x;
}
}
return ret;
}
pair<int, bool> dfs(int node){
//cout << "dfs " << node << "\n";
used[node] = true;
pair<int, bool> ret{node, false};
for(int idx: adj_dsu[node]){
int to;
if(dsu.get_p(edges[idx].first) == node) to = dsu.get_p(edges[idx].second);
else to = dsu.get_p(edges[idx].first);
if(used[to])
continue;
depth[to] = depth[node] + 1;
pair<int, bool> curr = dfs(to);
if(depth[curr.first] <= depth[node]) ans[idx] = (curr.second ^ (dsu.get_p(edges[idx].first) == node)) ? 'R' : 'L';
if(depth[curr.first] < depth[ret.first]) ret = curr;
}
for(auto p: ve[node]){
if(depth[p.first] == -1) continue;
//cout << node << " nodenonde " << p.first << " " << p.second << "\n";
if(depth[p.first] < depth[ret.first]) ret = p;
}
//cout << "return " << node << " - " << ret.first << " " << ret.second << "\n";
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
adjacent[u].push_back({v, i});
adjacent[v].push_back({u, i});
ans[i] = 'U';
edges[i] = {u, v};
}
for(int i = 1; i <= n; ++i){
if(!used[i]){
depth[i] = 0;
cycle(i, -1);
}
}
dsu.resize(n);
for(int i = 0; i < m; ++i)
if(ans[i] == 'B')
dsu.unite(edges[i].first, edges[i].second);
for(int i = 0; i < m; ++i){
if(ans[i] == 'U'){
int pf = dsu.get_p(edges[i].first), ps = dsu.get_p(edges[i].second);
adj_dsu[pf].push_back(i);
adj_dsu[ps].push_back(i);
adj2[pf].push_back(ps);
adj2[ps].push_back(pf);
}
}
cin >> p;
for(int i = 0; i < p; ++i){
int u, v;
cin >> u >> v;
int pu = dsu.get_p(u), pv = dsu.get_p(v);
if(pu != pv){
int lca = get_lca(pu, pv);
if(lca == pu || lca == pv){
ve[pu].push_back({pv, true});
ve[pv].push_back({pu, false});
}
else{
ve[pu].push_back({lca, true});
ve[pv].push_back({lca, false});
}
}
}
for(int i = 1; i <= n; ++i){
used[i] = false;
depth[i] = -1;
}
for(int i = 1; i <= n; ++i){
int pi = dsu.get_p(i);
if(!used[pi]){
depth[pi] = 0;
dfs(pi);
}
}
for(int i = 0; i < m; ++i)
if(ans[i] == 'U')
ans[i] = 'B';
for(int i = 0; i < m; ++i)
cout << ans[i];
cout << "\n";
}
Compilation message
oneway.cpp: In function 'int cycle(int, int)':
oneway.cpp:105:14: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto [to, idx]: adjacent[node]){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9856 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
9856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9856 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
9856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
9728 KB |
Output is correct |
| 2 |
Correct |
7 ms |
9728 KB |
Output is correct |
| 3 |
Correct |
7 ms |
9856 KB |
Output is correct |
| 4 |
Incorrect |
6 ms |
9856 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
