#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const ll mod = 1e9 + 7, inf = 1e9, mxv = 1005, mxn = 2e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, p;
int num[mxn + 1], low[mxn + 1], tt = 0, comp = 0, idcomp[mxn + 1], dep[mxn + 1];
int toedge[mxn + 1], pup[mxn + 1], pdown[mxn + 1], up[mxn + 1][17], ans[mxn + 1];
bool vis[mxn + 1], bridge[mxn + 1];
vt<pii>adj[mxn + 1], g[mxn + 1];
void dfs(int s, int pre){
low[s] = num[s] = ++tt;
for(int i = 0; i < sz(adj[s]); i++){
int v = adj[s][i].first, id = adj[s][i].second;
if(id % m == pre % m)continue;
if(!num[v]){
dfs(v, id);
low[s] = min(low[s], low[v]);
if(low[v] > num[s]){
bridge[id] = 1;
if(id < m)bridge[id + m] = 1;
else bridge[id - m] = 1;
}
}else low[s] = min(low[s], num[v]);
}
}
void dfs2(int s){
idcomp[s] = comp; vis[s] = 1;
for(int i = 0; i < sz(adj[s]); i++){
int v = adj[s][i].first, id = adj[s][i].second;
if(!bridge[id] && !vis[v]){
dfs2(v);
}
}
}
void dfs3(int s, int pre){
vis[s] = 1;
for(int i = 0; i < sz(g[s]); i++){
int v = g[s][i].first, id = g[s][i].second;
if(v == pre)continue;
dep[v] = dep[s] + 1;
up[v][0] = s; toedge[v] = id;
dfs3(v, s);
}
}
int lca(int u, int v){
if(dep[u] < dep[v])swap(u, v);
int k = dep[u] - dep[v];
for(int i = 0; i < 17; i++){
if(k & (1 << i)){
u = up[u][i];
}
}
if(u == v)return(u);
for(int i = 16; i >= 0; i--){
if(up[u][i] != up[v][i]){
u = up[v][i]; v = up[v][i];
}
}
return(up[u][0]);
}
void dfs4(int s, int pre){
for(int i = 0; i < sz(g[s]); i++){
int v = g[s][i].first, id = g[s][i].second;
if(v == pre)continue;
dfs4(v, s);
pup[s] += pup[v]; pdown[s] += pdown[v];
}
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
for(int i = 0; i < m; i++){
int u, v; cin >> u >> v;
adj[u].pb(make_pair(v, i)); adj[v].pb(make_pair(u, i + m));
}
for(int i = 1; i <= n; i++){
if(!num[i]){
dfs(i, -1);
}
}
for(int i = 1; i <= n; i++){
if(!vis[i]){
comp++;
dfs2(i);
}
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < sz(adj[i]); j++){
int v = adj[i][j].first, id = adj[i][j].second;
if(idcomp[i] != idcomp[v]){
g[idcomp[i]].pb(make_pair(idcomp[v], id));
}
}
}
for(int i = 1; i <= comp; i++){
vis[i] = 0; toedge[i] = -1;
sort(g[i].begin(), g[i].end());
g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
}
vt<int>root;
for(int i = 1; i <= comp; i++){
if(!vis[i]){
root.pb(i);
dfs3(i, -1);
}
}
for(int i = 1; i < 17; i++){
for(int j = 1; j <= comp; j++){
up[j][i] = up[up[j][i - 1]][i - 1];
}
}
cin >> p;
for(int i = 0; i < p; i++){
int u, v; cin >> u >> v;
u = idcomp[u]; v = idcomp[v];
if(u == v)continue;
int l = lca(u, v);
pup[u]++; pdown[v]++; pup[l]--; pdown[l]--;
}
for(int i = 0; i < sz(root); i++){
dfs4(root[i], -1);
}
for(int i = 1; i <= comp; i++){
if(pup[i]){
assert(!pdown[i]);
ans[toedge[i] % m] = 1 + ((toedge[i] / m) ^ 1);
}else if(pdown[i]){
ans[toedge[i] % m] = 1 + (toedge[i] / m);
}
}
for(int i = 0; i < m; i++){
if(ans[i] == 0)cout << 'B';
else if(ans[i] == 1)cout << 'R';
else cout << 'L';
}
return(0);
}
Compilation message
oneway.cpp: In function 'void dfs4(int, int)':
oneway.cpp:81:32: warning: unused variable 'id' [-Wunused-variable]
81 | int v = g[s][i].first, id = g[s][i].second;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9908 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9868 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9908 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9868 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
9684 KB |
Output is correct |
| 2 |
Correct |
4 ms |
9684 KB |
Output is correct |
| 3 |
Correct |
5 ms |
9908 KB |
Output is correct |
| 4 |
Incorrect |
5 ms |
9868 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
