// Source: https://usaco.guide/general/io
#include <bits/stdc++.h>
using namespace std;
vector<array<int , 2>> es;
vector<vector<array<int , 2>>> g1;
vector<int> comp , l, ti;
stack<int> u;
int t = 1 , c = 0;
void dfs(int p , int b){
l[p] = ti[p] = t++;
u.push(p);
for(auto [x , i]: g1[p]){
if(b == i)continue;
if(ti[x] == 0){
dfs(x , i);
if(l[x] > ti[p]){
while(true){
comp[u.top()] = c;
if(u.top() == x){
u.pop();
break;
}
u.pop();
}
c++;
}
l[p] = min(l[p] , l[x]);
continue;
}
l[p] = min(l[p] , ti[x]);
}
}
vector<vector<array<int , 2>>> g2;
vector<bool> vis;
void dfs(int p){
vis[p] = 1;
for(auto [x , i]: g1[p]){
if(vis[x])continue;
if(comp[x] != comp[p]){
g2[comp[x]].push_back({comp[p] , i});
g2[comp[p]].push_back({comp[x] , i});
//cout << comp[x] << " " << comp[p] << endl;
}
dfs(x);
}
}
vector<array<int , 28>> bl;
vector<int> f;
vector<array<int , 2>> k;
void bls(int p , int e , int y){
bl[p][0] = e;
//cout << p << " " << e << endl;
if(e==-1)f[p] = 0;else f[p] = f[e]+1;
k[p][0] = e;
k[p][1] = y;
for(int i = 1; i < 28; i++){
if(bl[p][i-1] == -1){
bl[p][i] = -1;
continue;
}
bl[p][i] = bl[bl[p][i-1]][i-1];
}
for(auto [x, i] : g2[p]){
if(x==e)continue;
bls(x , p , i);
}
}
int get(int a , int b){
if(f[a] < f[b])swap(a , b);
for(int i = 27; i >=0; i--){
if((1<<i) <= f[a]-f[b])a = bl[a][i];
}
if(a==b)return a;
for(int i = 27; i >=0; i--){
if(bl[a][i] != bl[b][i]){
a = bl[a][i];
b = bl[b][i];
}
}
return bl[a][0];
}
vector<array<int , 3>> v;
vector<int> ans;
void solve(int i){
//cout << v[i][0] << " " << v[i][1] << " " << v[i][2] << endl;
int a = v[i][1];
while(f[a] != v[i][0]){
if(ans[k[a][1]] != 0)break;
//cout << a << " " << k[a][0] << " " << k[a][1] << endl;
if(comp[es[k[a][1]][0]] == a){
ans[k[a][1]] = v[i][2];
}else{
ans[k[a][1]] = v[i][2]*-1;
}
a = k[a][0];
}
}
int main() {
int n , m; cin >> n >> m;
g1.resize(n);
comp.resize(n);
l.resize(n);
ti.resize(n);
for(int i = 0; i < m; i++){
int a , b; cin >> a >> b;
g1[a-1].push_back({b-1 , i});
g1[b-1].push_back({a-1 , i});
es.push_back({a-1 , b-1});
}
dfs(0 , -1);
while(!u.empty()){
comp[u.top()] = c;
u.pop();
}
c++;
g2.resize(c);
vis.resize(n , false);
dfs(0);
/*
for(int i = 0; i < n; i++){
cout << comp[i] << " ";
}
*/
bl.resize(c);
k.resize(c);
f.resize(c);
bls(0 , -1 , -1);
int q; cin >> q;
for(int i = 0; i < q; i++){
int a , b; cin >> a >> b;
a--;
b--;
int d = get(comp[a] , comp[b]);
v.push_back({f[d] , comp[a] , -1});
v.push_back({f[d] , comp[b] , 1});
}
sort(v.begin() , v.end());
ans.resize(m, 0);
for(int i = 0; i < v.size(); i++){
solve(i);
}
//cout << "a "<<endl;
for(int x : ans){
if(x == 0)cout << "B";
if(x == 1)cout << "L";
if(x == -1)cout << "R";
}
}
Compilation message
oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:15:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
15 | for(auto [x , i]: g1[p]){
| ^
oneway.cpp: In function 'void dfs(int)':
oneway.cpp:42:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
42 | for(auto [x , i]: g1[p]){
| ^
oneway.cpp: In function 'void bls(int, int, int)':
oneway.cpp:69:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
69 | for(auto [x, i] : g2[p]){
| ^
oneway.cpp: In function 'int main()':
oneway.cpp:147:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i = 0; i < v.size(); i++){
| ~~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
