#include <stack>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>
using namespace std;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 200005
int n, m, p;
basic_string<pair<int, int>> g[N];
int tin[N], low[N], timer; char ans[N];
int grp[N], twoedgecc;
stack<int> sd;
void tarjan(int u, int p)
{
tin[u] = low[u] = ++timer;
sd.push(u);
for (auto [v, _] : g[u])
{
if (v == p)
{
p = -1;
continue;
}
if (!tin[v]) tarjan(v, u);
low[u] = min(low[u], low[v]);
}
if (tin[u] == low[u])
{
int v;
do grp[v = sd.top()] = twoedgecc, sd.pop();
while (v != u);
++twoedgecc;
}
}
basic_string<pair<int, int> > G[N];
int aux[N], sz[N], ch[N], ci[N], P[20][N], hv[N], hveid[N], dep[N];
int dfs(int u, int p)
{
int sz = 1;
P[0][u] = p;
for (int j = 1; j < 18; ++j) P[j][u] = P[j-1][P[j-1][u]];
int hvsz = -1;
for (auto [v, _] : G[u]) if (v != p)
{
dep[v] = dep[u] + 1;
int sub = dfs(v, u); sz += sub;
if (sub > hvsz) hv[u] = v, hvsz = sub, hveid[u] = _;
}
}
int ctimer;
void hld(int u, int h, int pd)
{
ci[u] = ctimer++; ch[u] = h; aux[u] = pd;
if (hv[u]) hld(hv[u], h, hveid[u]);
for (auto [v, _] : G[u]) if (v != P[0][u] and v != hv[u]) hld(v, v, _);
}
int lca(int u, int v)
{
if (dep[u] < dep[v]) swap(v, u);
int dt = dep[u] - dep[v];
for(int j=18;j--;)if(dt&(1<<j))u=P[j][u];
if(u==v)return u;
for(int j=18;j--;)if(P[j][u]-P[j][v])u=P[j][u],v=P[j][v];
return P[0][u];
}
char whatt[N<<1], lz[N<<1];
void _push(int v, int l, int r)
{
if (lz[v])
{
whatt[v]=lz[v];
if (l-r)
{
auto m=(l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
lz[vl]=lz[vr]=lz[v];
}
lz[v]=0;
}
}
void _set(int v, int l, int r,int x,int y,int k)
{
_push(v,l,r);
if(r<x or y<l)return;
if(x<=l and r<=y){lz[v]=k;_push(v,l,r);return;}
auto m=(l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
_set(vl,l,m,x,y,k);_set(vr,m+1,r,x,y,k);
}
char _qry(int v,int l, int r, int p)
{
_push(v,l,r);
if(l==r)return whatt[v];
auto m=(l+r)/2,vl=v+1,vr=v+(m-l+1)*2;
if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
}
void updup(int u, int a, int d)
{
for (; ch[u] != ch[a]; u = P[0][ch[u]]) _set(0, 0, ctimer, ci[ch[u]], ci[u], d);
_set(0, 0, ctimer, ci[a], ci[u], d);
}
int main()
{
ShinLena;
cin >> n >> m;
for (int u, v, i = 1; i <= m; ++i)
cin >> u >> v, g[u].push_back({v, i}), g[v].push_back({u, -i}), ans[i] = 'B';
for (int i = 1; i <= n; ++i) if (!tin[i]) tarjan(i, -1);
for (int u = 1; u <= n; ++u)
for (auto [v, eid] : g[u])
if (eid > 0 and grp[u] != grp[v])
G[grp[u]].push_back({grp[v], eid}), G[grp[v]].push_back({grp[u], -eid});
for (int i = 0; i < twoedgecc; ++i) sort(ALL(G[i])), G[i].resize(unique(ALL(G[i])) - G[i].begin());
for (int i = 0; i < twoedgecc; ++i) if (!P[0][i]) dfs(i, -1), hld(i, i, 0);
_set(0, 0, ctimer, 0, ctimer, 'B');
cin >> p;
for (int x, y, i = 0; i < p; ++i)
{
cin >> x >> y;
if ((x = grp[x]) == (y = grp[y])) continue;
int a = lca(x, y);
int X = _qry(0,0,ctimer,ci[a]);
updup(x, a, 'L');
updup(y, a, 'R');
_set(0,0,ctimer,ci[a],ci[a],X);
}
for (int i = 0; i < twoedgecc; ++i)
{
ans[abs(aux[i])] = _qry(0,0,ctimer,ci[i]);
if (aux[i] < 0)
{
aux[i] *= -1;
if (ans[aux[i]] == 'L') ans[aux[i]] = 'R';
else if (ans[aux[i]] == 'R') ans[aux[i]] = 'L';
}
}
cout << (ans+1);
return 0;
}
Compilation message
oneway.cpp: In function 'int dfs(int, int)':
oneway.cpp:73:1: warning: no return statement in function returning non-void [-Wreturn-type]
73 | }
| ^
oneway.cpp: In function 'char _qry(int, int, int, int)':
oneway.cpp:122:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
122 | if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
| ^~
oneway.cpp:122:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
122 | if(p<=m)return _qry(vl,l,m,p); return _qry(vr,m+1,r,p);
| ^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
485 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
485 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
485 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
