#include<bits/stdc++.h>
using namespace std;
#ifdef ONPC
#include"debug.h"
#else
#define debug(...) 42
#endif
#define endl '\n'
#define ll long long
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
const int MAXN = 1e5 + 15;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m;
vector<pii> adj[MAXN];
int id[MAXN], fa[MAXN][20];
int dep[MAXN];
int dir[2][MAXN];
bool vis[MAXN];
void dfs1(int node, int par){
debug(node, par);
vis[node] = 1;
fa[node][0] = par;
dep[node] = dep[par] + 1;
for (int b = 1; b < 20; b++){
fa[node][b] = fa[fa[node][b - 1]][b - 1];
}
for (auto [to, idx] : adj[node]){
if (idx == id[node]) continue;
if (vis[to]) {
if (dep[to] < dep[node]){
debug(node, to, par, "!");
dir[0][node] += 1;
dir[0][to] -= 1;
dir[1][node] += 1;
dir[1][to] -= 1;
}
}
else {
id[to] = idx;
dfs1(to, node);
}
}
}
void dfs3(int node){
vis[node] = 1;
for (auto [to, idx] : adj[node]){
if (vis[to]) continue;
dfs3(to);
dir[0][node] += dir[0][to];
dir[1][node] += dir[1][to];
}
}
int LCA(int u, int v){
if (dep[u] > dep[v]) swap(u, v);
for (int b = 19; b >= 0; b--){
if (dep[fa[v][b]] >= dep[u]) v = fa[v][b];
}
if (u == v) return u;
for (int b = 19; b >= 0; b--){
if (fa[u][b] != fa[v][b]){
u = fa[u][b];
v = fa[v][b];
}
}
return fa[u][0];
}
int ans[MAXN];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
vector<pii> edges(m + 1);
for (int i = 0; i < m; i++){
int u, v;
cin >> u >> v;
edges[i + 1] = {u, v};
adj[u].pb({v, i + 1});
adj[v].pb({u, i + 1});
}
dfs1(1, 1);
for (int i = 0; i <= n; i++){
debug(i, dir[0][i], dir[1][i]);
}
debug("E");
int q;
cin >> q;
while (q--){
int u, v;
cin >> u >> v;
int lca = LCA(u, v);
dir[0][u] += 1;
dir[0][lca] -= 1;
dir[1][v] += 1;
dir[1][lca] -= 1;
debug(u, v, lca);
// u -> lca up
// v -> lca down
}
memset(vis, 0, sizeof(vis));
dfs3(1);
memset(ans, -1, sizeof(ans));
for (int i = 1; i <= n; i++){
debug(i, dir[0][i], dir[1][i]);
if ((!!dir[0][i])^(!!dir[1][i])){
if (dir[1][i]){
ans[id[i]] = (edges[id[i]].F == fa[i][0]);
}
if (dir[0][i]){
ans[id[i]] = (edges[id[i]].F == i);
}
}
}
for (int i = 1; i <= m; i++){
if (ans[i] == -1){
cout << 'B';
} else if (ans[i] == 1) {
cout << 'R';
}
else {
cout << 'L';
}
}
}
Compilation message
oneway.cpp: In function 'void dfs1(int, int)':
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 42
| ^~
oneway.cpp:29:2: note: in expansion of macro 'debug'
29 | debug(node, par);
| ^~~~~
oneway.cpp:36:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
36 | for (auto [to, idx] : adj[node]){
| ^
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 42
| ^~
oneway.cpp:40:5: note: in expansion of macro 'debug'
40 | debug(node, to, par, "!");
| ^~~~~
oneway.cpp: In function 'void dfs3(int)':
oneway.cpp:56:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
56 | for (auto [to, idx] : adj[node]){
| ^
oneway.cpp: In function 'int main()':
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 42
| ^~
oneway.cpp:93:3: note: in expansion of macro 'debug'
93 | debug(i, dir[0][i], dir[1][i]);
| ^~~~~
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 42
| ^~
oneway.cpp:95:2: note: in expansion of macro 'debug'
95 | debug("E");
| ^~~~~
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 42
| ^~
oneway.cpp:106:3: note: in expansion of macro 'debug'
106 | debug(u, v, lca);
| ^~~~~
oneway.cpp:6:20: warning: statement has no effect [-Wunused-value]
6 | #define debug(...) 42
| ^~
oneway.cpp:114:3: note: in expansion of macro 'debug'
114 | debug(i, dir[0][i], dir[1][i]);
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
