#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int MOD = (int)1e9 + 7;
const int MAXN = (int)1e5 + 7;
const int infint = (int)1e9;
int visited[MAXN], is[MAXN], dp[MAXN], h[MAXN], n, m, par[MAXN], p[MAXN][20], up[MAXN], down[MAXN];
set< pair<int, int> > D;
pair<int, int> edge[MAXN];
vector<pair<int, int> > adj[MAXN];
vector<int> T[MAXN];
void dfs(int v, int index)
{
dp[v] = h[v];
visited[v] = 1;
for(auto u : adj[v])
{
if(!visited[u.first])
{
h[u.first] = h[v] + 1;
dfs(u.first, u.second);
dp[v] = min(dp[v], dp[u.first]);
}
else
{
if(index != u.second)
dp[v] = min(dp[v], h[u.first]);
}
}
if(v != 1)
{
if(dp[v] == h[v])
is[index] = 1;
}
return;
}
int get(int u)
{
return par[u] < 0 ? u : par[u] = get(par[u]);
}
void merge(int u, int v)
{
if((u = get(u)) == (v = get(v)))
return;
if(par[u] > par[v])
swap(u, v); //par[u] > par[v]
par[u] += par[v];
par[v] = u;
}
void add(int u, int v)
{
T[u].push_back(v);
T[v].push_back(u);
}
void dfs_pre(int u, int P)
{
visited[u] = 1, p[u][0] = P;
for (auto v : T[u])
if(v != P)
{
h[v] = h[u] + 1;
dfs_pre(v, u);
}
}
int lca(int u, int v)
{
if(h[u] > h[v])
swap(u, v);
for (int i = 19; i >= 0; i--)
if(h[v] - (1ll << i) >= h[u])
v = p[v][i];
if(u == v)
return u;
for (int i = 19; i >= 0; i--)
if(p[v][i] != p[u][i] && p[u][i] != -1 && p[v][i] != -1)
v = p[v][i], u = p[u][i];
return p[v][0];
}
void dfs_col(int u, int P)
{
for (auto v : T[u])
if(v != P)
{
dfs_col(v, u);
down[u] += down[v];
up[u] += up[v];
}
if(down[u])
D.insert({P, u});
if(up[u])
D.insert({u, P});
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> edge[i].first >> edge[i].second;
adj[edge[i].first].push_back({edge[i].second, i});
adj[edge[i].second].push_back({edge[i].first, i});
}
dfs(1, 0);
memset(par, -1, sizeof par);
for (int i = 0; i < m; i++)
if(!is[i])
merge(edge[i].first, edge[i].second);
for (int i = 0; i < m; i++)
if(get(edge[i].first) != get(edge[i].second))
{
int u = get(edge[i].first), v = get(edge[i].second);
add(u, v);
}
memset(visited, 0, sizeof visited);
memset(h, 0, sizeof h);
memset(p, -1, sizeof p);
for (int i = 1; i <= n; i++)
if(!visited[i])
{
add(0, i);
h[i] = 1;
dfs_pre(i, 0);
}
for (int i = 1; i < 20; i++)
for (int j = 1; j <= n; j++)
if(p[j][i - 1] != -1)
p[j][i] = p[p[j][i - 1]][i - 1];
//derakht moalefeyae yal hambandesho gereftim.
int q;
cin >> q;
for (int i = 0; i < q; i++)
{
int x, y;
cin >> x >> y;
x = get(x), y = get(y);
int c = lca(x, y);
up[x]++, up[c]--;
down[y]++, down[c]--;
}
dfs_col(0, -1);
for (int i = 0; i < m; i++)
{
int u = get(edge[i].first), v = get(edge[i].second);
if(u == v)
cout << 'B';
else
if(D.count({u, v}))
cout << 'R';
else
if(D.count({v, u}))
cout << 'L';
else
cout << 'B';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
14072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
14072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
13 ms |
14072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
