#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pf push_front
#define fi first
#define se second
const ll mod = 1e9+7, mxn = 1e5+7;
ll id[mxn], dir[mxn];
struct bridge_tree
{
ll n, m, tdfs, cnt;
vector<ll> tin, comp, low, h, u_dir, d_dir;
vector<vector<ll>> up;
vector<bool> used, is_bridge, vis;
vector<vector<pair<ll,ll>>> g;
vector<vector<pair<ll,ll>>> b_tree;
vector<pair<ll,ll>> ed;
bridge_tree() {}
bridge_tree(ll nn, ll mm)
{
n = nn; m = mm;
tdfs = cnt = 0;
tin.resize(n+7); comp.resize(n+7); low.resize(n+7);
used.resize(n+7); is_bridge.resize(m+7);
g.resize(n+7); b_tree.resize(n+7); ed.resize(m+7);
h.resize(n+7); up.resize(n+7,vector<ll>(20));
u_dir.resize(n+7); d_dir.resize(n+7); vis.resize(n+7);
}
void get_tree()
{
for (ll i = 1; i <= m; i++)
{
ll a, b; cin >> a >> b;
g[a].pb({b,i}); g[b].pb({a,i});
ed[i] = {a,b};
}
}
void dfs(ll u, ll v)
{
tin[u] = low[u] = ++tdfs;
used[u] = 1;
for (pair<ll,ll> i : g[u])
{
if (i.se != v)
{
if (used[i.fi]) low[u] = min(low[u], tin[i.fi]);
else
{
dfs(i.fi, i.se);
low[u] = min(low[u], low[i.fi]);
if (low[i.fi] == tin[i.fi]) is_bridge[i.se] = 1;
}
}
}
}
void decompose(ll u, ll v)
{
used[u] = 1; comp[u] = cnt;
for (pair<ll,ll> i : g[u]) if (!is_bridge[i.se] && !used[i.fi]) decompose(i.fi,u);
}
void build()
{
get_tree();
for (ll i = 1; i <= n; i++) if (!used[i]) dfs(i,i);
for (ll i = 1; i <= n; i++) used[i] = 0;
for (ll i = 1; i <= n; i++) if (!used[i]) {cnt++; decompose(i,i);}
for (ll i = 1; i <= m; i++)
{
if (comp[ed[i].fi] != comp[ed[i].se])
{
b_tree[comp[ed[i].fi]].pb({comp[ed[i].se],i});
b_tree[comp[ed[i].se]].pb({comp[ed[i].fi],-i});
}
}
// g.clear(); ed.clear(); used.clear(); is_bridge.clear();
// tin.clear(); comp.clear(); low.clear();
}
void dfs_lca(ll u, ll v)
{
vis[u] = 1;
for (pair<ll,ll> i : b_tree[u])
{
if (i.fi != v)
{
h[i.fi] = h[u]+1; up[i.fi][0] = u;
dfs_lca(i.fi,u);
}
}
}
void build_lca()
{
for (ll i = 1; i <= cnt; i++) if (!vis[i]) dfs_lca(i,i);
for (ll i = 1; i <= cnt; i++)
{
for (ll j = 1; j <= 19; j++) up[i][j] = up[up[i][j-1]][j-1];
}
}
ll lca(ll a, ll b)
{
if (h[a] != h[b])
{
if (h[a] < h[b]) swap(a,b);
ll k = h[a]-h[b];
for (ll i = __lg(k); i >= 0; i--)
{
if (k >> i & 1) a = up[a][i];
}
}
if (a == b) return a;
for (ll i = 19; i >= 0; i--)
{
if (up[a][i] != up[b][i]) {a = up[a][i]; b = up[b][i];}
}
return up[a][0];
}
void update(ll x, ll y)
{
x = comp[x]; y = comp[y];
ll l = lca(x, y);
// cerr << x << ' ' << l << ' ' << y << '\n';
u_dir[x]++; u_dir[l]--;
d_dir[y]++; d_dir[l]--;
}
void full_update(ll u, ll v)
{
vis[u] = 1;
for (pair<ll,ll> i : b_tree[u])
{
if (i.fi != v && !vis[i.fi])
{
full_update(i.fi,u);
u_dir[u] += u_dir[i.fi];
d_dir[u] += d_dir[i.fi];
id[i.fi] = i.se;
}
}
}
};
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("test.inp","r",stdin); freopen("test.out","w",stdout); freopen("test.err","w",stderr);
ll n, m; cin >> n >> m;
bridge_tree bt(n, m); bt.build(); bt.build_lca();
ll q; cin >> q;
while (q--)
{
ll x, y; cin >> x >> y;
// if (bt.comp[x] == bt.comp[y]) continue;
bt.update(x,y);
}
// cerr << bt.cnt << '\n';
// for (ll i = 1; i <= n; i++) cerr << bt.comp[i] << ' ';
// cerr << '\n';
for (ll i = 1; i <= bt.cnt; i++) bt.vis[i] = 0;
for (ll i = 1; i <= bt.cnt; i++) if (!bt.vis[i]) bt.full_update(i,i);
for (ll i = 1; i <= n; i++)
{
if (bt.u_dir[i] && bt.d_dir[i]) continue;
ll idx = id[i];
// cerr << i << ' ' << idx << '\n';
if (bt.u_dir[i])
{
// cerr << "U" << '\n';
if (idx > 0) dir[idx] = 1;
else dir[-idx] = -1;
}
if (bt.d_dir[i])
{
// cerr << "D" << '\n';
if (idx > 0) dir[idx] = -1;
else dir[-idx] = 1;
}
}
for (ll i = 1; i <= m; i++)
{
if (dir[i] < 0) cout << "R";
else if (dir[i] > 0) cout << "L";
else cout << "B";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
1 ms |
604 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
860 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
