#include<bits/stdc++.h>
using namespace std;
#define maxn 100001
#define f first
#define s second
int n, q, timedfs = 1, ccnt = 0, m;
int sprasetable[maxn][18];
stack<int> s;
vector<vector<pair<int, int>>> graph;
vector<vector<pair<int, int>>> tree;
vector<int> edgeup;
vector<pair<int, int>> edge;
vector<int> ans;
int level[maxn];
int low[maxn];
int up[maxn];
int pos[maxn];
int num[maxn];
void build(int x){
if((1<<x) > n)return;
for(int i = 0; i <= n; i++){
if(sprasetable[i][x-1] != -1)sprasetable[i][x] = sprasetable[sprasetable[i][x-1]][x-1];
else sprasetable[i][x] = -1;
}
build(x+1);
}
void DFSt(int x, int p){
low[x]=num[x]=timedfs++;
s.push(x);
for(auto u: graph[x]){
if(u.s == p)continue;
if(!num[u.f])DFSt(u.f, u.s);
else{
if(num[u.f] < num[x])low[x]=min(low[x], low[u.f]);
else low[u.f]=min(low[u.f], num[x]);
}
}
if(low[x] == num[x]){
ccnt++;
while(s.top() != x){
pos[s.top()]=ccnt;
s.pop();
}
pos[s.top()]=ccnt;
s.pop();
}
}
int travelup(int x, int distance){
for(int i = 0; i < 20; i++){
if(bool(distance & (1 << i)))x = sprasetable[x][i];
if(x == -1)return -1;
}
return x;
}
int query(int a, int b){
if(level[a] < level[b])swap(a, b);
int distance = level[a]-level[b];
a = travelup(a, distance);
int curr = 0;
while(sprasetable[a][curr] != sprasetable[b][curr])curr++;
for(int i = curr; i >= 0; i--){
if(sprasetable[a][i] != sprasetable[b][i]){
a = sprasetable[a][i];
b = sprasetable[b][i];
}
}
if(a == b)return a;
else return sprasetable[a][0];
}
void DFS(int x, int p){
sprasetable[x][0]=p;
for(auto u: tree[x]){
if(u.f == p)continue;
level[u.f]=level[x]+1;
edgeup[u.f]=u.s;
DFS(u.f, x);
}
}
int Find(int x){
if(up[x] < 0)return x;
else{
up[x]=Find(up[x]);
return up[x];
}
}
void Union(int a, int b){
a = Find(a);
b = Find(b);
up[a]=b;
}
int main(){
cin >> n >> m;
graph.resize(n+1);
edge.resize(m);
ans.assign(m, 0);
for(int i = 0; i < m; i++){
int a, b;
cin >> a >> b;
graph[a].push_back({b, i});
graph[b].push_back({a, i});
edge[i]={a, b};
}
DFSt(1, -1);
graph.clear();
edgeup.resize(n+1);
tree.resize(ccnt+1);
for(int i = 0; i < m; i++){
int a = pos[edge[i].f];
int b = pos[edge[i].s];
if(a != b){
tree[a].push_back({b, i});
tree[b].push_back({a, i});
}
}
for(int i = 1; i <= ccnt; i++)if(!sprasetable[i][0])DFS(1, -1);
for(int i = 1; i <= ccnt; i++)up[i]=-1;
build(1);
cin >> q;
for(int i = 0; i < q; i++){
int a, b;
cin >> a >> b;
a=pos[a];
b=pos[b];
int anc = query(a, b);
a = Find(a);
while(level[anc] < level[a]){
ans[edgeup[a]]=1;
Union(a, sprasetable[a][0]);
a = sprasetable[a][0];
a = Find(a);
}
b = Find(b);
while(level[anc] < level[b]){
ans[edgeup[b]]=-1;
Union(b, sprasetable[b][0]);
b = sprasetable[b][0];
b = Find(b);
}
}
for(int i = 0; i < m; i++){
if(!ans[i])cout << "B";
else{
int tmp = ans[i];
if(edgeup[pos[edge[i].f]] == i)tmp*=-1;
if(tmp == 1)cout << "L";
else cout << "R";
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
271 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
271 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
271 ms |
262148 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
