#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
#define MAXN 101010
vpi V[MAXN];
int N,E,a,b;
int p[MAXN];
int W[MAXN];
stack<int> stk;
int lowlink[MAXN], bcc[MAXN], depth[MAXN];
vpi A[MAXN];
int out[MAXN];
int indextopar[MAXN];
int pp[MAXN];
vpi edges;
void dfs(int x, int w){
depth[x] = lowlink[x] = a++;
stk.push(x);
for (auto i : V[x])if(i.s != w){
if (p[i.f]){
lowlink[x] = min(lowlink[x], lowlink[i.f]);
continue;
}
p[i.f] = x;
dfs(i.f,i.s);
lowlink[x] = min(lowlink[x], lowlink[i.f]);
}
if (lowlink[x] == depth[x]){
while(stk.top() != x){
bcc[stk.top()] = b;
stk.pop();
}
stk.pop();
bcc[x] = b++;
}
}
void d2(int x){
for (auto v:A[x])if(v.f != pp[x]){
pp[v.f] = x;
depth[v.f] = depth[x]+1;
indextopar[v.f] = v.s;
d2(v.f);
}
}
int par(int x){return (p[x] == x)?x:p[x] = par(p[x]);}
int main(){
cin>>N>>E;
for (int i=0;i<E;++i){
cin>>a>>b;
V[a].pb(b,i);
V[b].pb(a,i);
edges.pb(a,b);
}
a=1;b=1;
p[1] = 1;
dfs(1,-1);
// for (int i=1;i<=N;++i)cout<<bcc[i]<<' ';cout<<'\n';
N = b-1;
for (int i=0;i<SZ(edges);++i){
a = bcc[edges[i].f];
b = bcc[edges[i].s];
if (a == b){
out[i] = -1;
continue;
}
A[a].pb(b,i);
A[b].pb(a,i);
// cout<<a<<' '<<b<<' '<<i<<'\n';
}
memset(depth,0,sizeof(depth));
depth[1]=1;
d2(1);
for (int i=1;i<=N;++i)p[i]=i;
int Q;
cin>>Q;
while(Q--){
cin>>a>>b;
a=bcc[a];b=bcc[b];
if (a == b)continue;
while (1){
a = par(a);
b = par(b);
// cout<<a<<' '<<b<<'\n';
if (a == b)break;
if (depth[a] > depth[b]){
int target = indextopar[a];
// cout<<"Set "<<target<<" to "<<a<<'\n';
assert(out[target] == 0);
out[target] = pp[a];
p[a] = pp[a];
a = pp[a];
}else{
int target = indextopar[b];
assert(out[target] == 0);
out[target] = b;
// cout<<"Set "<<target<<" to "<<b<<'\n';
p[b] = pp[b];
b = pp[b];
}
}
// cout<<'\n';
}
// for (int i=0;i<E;++i)cout<<out[i]<<' ';
for (int i=0;i<E;++i){
if (out[i] == -1)cout<<"B";
else if (bcc[edges[i].f] == out[i])cout<<"L";
else if (bcc[edges[i].s] == out[i])cout<<"R";
else assert(0);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
11000 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
11000 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
16 ms |
11000 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
