#include <bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))
template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const int maxN = 1e5+10;
vector<int> edge[maxN];
int depth[maxN];
int low[maxN];
bool visited[maxN];
stack<int> st;
int bcc[maxN];
vector<int> t_edge[maxN];
void tarjan(int c, int p){
depth[c] = (p ? depth[p] + 1 : 0);
low[c] = depth[c];
visited[c] = true;
st.push(c);
int cnt_fa = 0;
for(int i : edge[c]){
if(i == p && !cnt_fa){
cnt_fa = 1;
continue;
}
if(visited[i]){
cmin(low[c], depth[i]);
}else{
tarjan(i, c);
cmin(low[c], low[i]);
}
}
if(low[c] == depth[c]){
int tmp = st.top();
do{
tmp = st.top();
bcc[tmp] = c;
st.pop();
}while(tmp != c);
}
}
int ST[18][maxN];
int fa[maxN];
pii tab[maxN];
char ans[maxN];
int dsu[2][maxN]; // 0 down, 1 up.
int query(int i, int a){
return dsu[i][a] == a ? a : dsu[i][a] = query(i, dsu[i][a]);
}
void merge(int i, int a, int b){
if(query(i, a) != query(i, b)) dsu[i][query(i, a)] = query(i, b);
}
int t_depth[maxN];
bool t_visited[maxN];
void dfs(int c, int p){
t_visited[c] = true;
t_depth[c] = ( p ? t_depth[p] + 1 : 0);
for(int i : t_edge[c]){
if(i == p) continue;
dfs(i, c);
}
}
int LCA(int x, int y){
if(t_depth[x] < t_depth[y]) swap(x,y);
int c = t_depth[x] - t_depth[y];
F(18) if( (c >> i) & 1) x = ST[i][x];
assert(t_depth[x] == t_depth[y]);
RF(18){
if( ST[i][x] && ST[i][y] && ST[i][x] != ST[i][y]){
x = ST[i][x];
y = ST[i][y];
}
}
x = ST[0][x];
y = ST[0][y];
assert( x == y );
return x;
}
void process(int x, int y){
int c = LCA(x,y);
while( depth[x] > depth[c] ){
if(dsu[1][x] != x){
dsu[1][x] = x;
}else{
merge(1, x, ST[0][x]);
x = ST[0][x];
}
}
while( depth[y] > depth[c] ){
if(dsu[0][y] != y){
dsu[0][y] = y;
}else{
merge(0, y, ST[0][y]);
y = ST[0][y];
}
}
}
signed main(){
iota(dsu[0], dsu[0] + maxN, 0);
iota(dsu[1], dsu[1] + maxN, 0);
int n, m;
cin >> n >> m;
F(m){
int x,y;
cin >> x >> y;
edge[x].pb(y);
edge[y].pb(x);
tab[i] = mp(x,y);
}
F(n) if(!visited[i+1]) tarjan(i+1, 0);
Fi(x, m){
auto [i,j] = tab[x];
if(bcc[i] != bcc[j]){
t_edge[bcc[i]].pb(bcc[j]);
t_edge[bcc[j]].pb(bcc[i]);
if(depth[bcc[i]] > depth[bcc[j]]){
ST[0][bcc[i]] = fa[bcc[i]] = bcc[j];
}else{
ST[0][bcc[j]] = fa[bcc[j]] = bcc[i];
}
//printf("(%d, %d)\n", bcc[i], bcc[j]);
}else{
ans[x] = 'B';
}
}
Fl(i, 1, n+1){
if(!t_visited[bcc[i]]) dfs( bcc[i], 0);
}
Fl(i, 1, 18){
Fi(j, maxN){
ST[i][j] = ST[i-1][ST[i-1][j]];
}
}
int p;
cin >> p;
F(p){
int x,y;
cin >> x >> y;
x = bcc[x], y = bcc[y];
process(x,y);
}
Fi(x, m){
auto[i,j] = tab[x];
i = bcc[i], j = bcc[j];
if(i != j){
if(query(0, i) == query(0, j)){
if(t_depth[i] < t_depth[j]){
ans[x] = 'R';
}else{
ans[x] = 'L';
}
}else if(query(1,i) == query(1, j)){
if(t_depth[i] < t_depth[j]){
ans[x] = 'L';
}else{
ans[x] = 'R';
}
}else{
ans[x] = 'B';
}
}
}
F(m) printf("%c", ans[i]);
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
12348 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12412 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12440 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12492 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
12628 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
12348 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12412 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12440 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12492 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
12628 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
12348 KB |
Output is correct |
| 2 |
Correct |
9 ms |
12412 KB |
Output is correct |
| 3 |
Correct |
9 ms |
12440 KB |
Output is correct |
| 4 |
Correct |
10 ms |
12492 KB |
Output is correct |
| 5 |
Incorrect |
12 ms |
12628 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
