#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int p[100005], low[100005], num[100005];
int ct = 1;
int n,m,q;
vector<int> G[100005];
vector<int> _G[200005];
int col[100005];
int brid[100005];
int d[100005];
int P[100005][20];
int U[100005], V[100005];
int ans[100005];
int cct = 1;
vector<ii> hm[100005];
vector<int> ord;
map<ii, int> countedg;
void dfs(int u){
low[u] = num[u] = ct++;
for (auto v : G[u]){
if (num[v] == -1){
p[v] = u;
dfs(v);
if (low[v] > num[u]){
//printf("%d %d is a bridge\n",u,v);
brid[v] = 1;
}
low[u] = min(low[u],low[v]);
}
else if (p[u] != v){
low[u] = min(low[u],num[v]);
}
}
}
void dfs2(int u){
for (auto v : G[u]){
if (p[v] == u){
if (brid[v] && countedg[ii(min(u,v),max(u,v))] == 1) continue;
col[v] = col[u];
dfs2(v);
}
}
}
void dfs3(int u){
ord.push_back(u);
for (auto v : _G[u]){
if (P[v][0] == -1){
//printf("%d -> %d\n",u,v);
P[v][0] = u;
d[v] = d[u]+1;
dfs3(v);
}
}
}
int lca(int u, int v){
if (d[u] < d[v]) swap(u,v);
int dif = d[u]-d[v];
for (int i = 0; i < 20; i++){
if (dif>>i&1){
u = P[u][i];
}
}
if (u == v) return u;
for (int i = 19; i >= 0; i--){
if (P[u][i] != -1 && P[v][i] != -1 && P[u][i] != P[v][i]){
u = P[u][i], v = P[v][i];
}
}
assert(P[u][0] == P[v][0]);
return P[u][0];
}
int main(){
scanf("%d%d",&n,&m);
memset(num,-1,sizeof(num));
for (int i = 0; i < m; i++){
scanf("%d%d",&U[i],&V[i]);
int che = ++countedg[ii(min(U[i],V[i]),max(U[i],V[i]))];
if (U[i] == V[i] || che > 1) continue;
G[U[i]].push_back(V[i]);
G[V[i]].push_back(U[i]);
}
dfs(1);
for (int i = 1; i <= n; i++){
if (col[i] == 0){
col[i] = cct++;
dfs2(i);
}
}
//for (int i = 1; i <= n; i++){ printf("%d ",col[i]); }
for (int u = 1; u <= n; u++){
for (auto v : G[u]){
if (col[v] != col[u]){
_G[col[u]].push_back(col[v]);
}
}
}
memset(P,-1,sizeof(P));
for (int i = 1; i < cct; i++){
if (P[i][0] == -1){
P[i][0] = i;
dfs3(i);
}
}
for (int k = 1; k < 20; k++){
for (int i = 1; i < cct; i++){
if (P[i][k-1] == -1) break;
P[i][k] = P[P[i][k-1]][k-1];
}
}
scanf("%d",&q);
for (int i = 0; i < q; i++){
int a, b;
scanf("%d%d",&a,&b);
if (col[a] == col[b]) continue;
else{
a = col[a];
b = col[b];
int c = lca(a,b);
//printf("%d %d %d\n",a,c,b);
if (c != a) hm[c].push_back({a,1});
if (c != b) hm[c].push_back({b,-1});
}
}
for (auto x: ord){
for (auto cur : hm[x]){
int u = cur.first, dir = cur.second;
while (ans[u] == 0 && u != x){
//printf("%d -> %d with %d\n",u,P[u][0],dir);
ans[u] = dir;
u = P[u][0];
}
}
}
for (int i = 0; i < m; i++){
int u = U[i], v = V[i];
if (col[u] == col[v]){
printf("B");
}
else{
u = col[u], v = col[v];
if (d[v] > d[u]){
if (ans[v] == 1) printf("L");
else if (ans[v] == -1) printf("R");
else printf("B");
}
else{
if (ans[u] == 1) printf("R");
else if (ans[u] == -1) printf("L");
else printf("B");
}
}
}
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&n,&m);
~~~~~^~~~~~~~~~~~~~
oneway.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&U[i],&V[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
oneway.cpp:114:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&a,&b);
~~~~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
18048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
18048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
15 ms |
18048 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
