#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pll;
typedef pair<pll, ll> tll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#pragma GCC optimize("Ofast")
#define pb push_back
#define eb emplace_back
#define f first
#define s second
const int maxn = 1e5 + 5;
vector<pll> adj[maxn];
int in[maxn], low[maxn], id[maxn], cnt[maxn], dfn = 1;
int n, m, gp = 0;
stack<int> stk;
void dfs(int pos, int idx){
in[pos] = low[pos] = dfn++;
stk.push(pos);
for(auto [x, index] : adj[pos]){
if(index % m == idx % m) continue;
if(!in[x]) dfs(x, index);
low[pos] = min(low[pos], low[x]);
}
if(in[pos] == low[pos]){
while(stk.top() != pos){
int x = stk.top(); stk.pop();
id[x] = gp;
}
stk.pop();
id[pos] = gp;
gp++;
}
}
string key = "RLB";
vector<pll> nadj[maxn];
int ncnt[maxn], ans[maxn];
void build_new_graph(){
for(int i = 0; i < n; i++){
ncnt[id[i]] += cnt[i];
for(auto [x, idx] : adj[i]){
if(id[x] == id[i]){
ans[idx % m] = 2;
}
else nadj[id[i]].eb(id[x], idx);
}
}
}
void dfsans(int pos, int prev){
for(auto [x, idx] : nadj[pos]){
if(idx % m == prev % m) continue;
dfsans(x, idx);
if(ncnt[x] > 0) ans[idx % m] = (idx < m ? 1 : 0);
else if(ncnt[x] < 0) ans[idx % m] = (idx < m ? 0 : 1);
else ans[idx % m] = 2;
ncnt[pos] += ncnt[x];
}
}
void solve(){
cin>>n>>m;
for(int i = 0; i < m; i++){
int a, b;
cin>>a>>b;
a--, b--;
adj[a].eb(b, i);
adj[b].eb(a, i + m);
}
int p;
cin>>p;
for(int i = 0; i < p; i++){
int a, b;
cin>>a>>b;
a--, b--;
cnt[a] ++, cnt[b] --;
}
//generate a cut-block-tree
dfs(0, -1);
build_new_graph();
dfsans(0, -1);
for(int i = 0; i < m; i++) cout<<key[ans[i]];
cout<<"\n";
}
int main(void){
fastio;
int t = 1;
// cin>>t;
while(t--){
solve();
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
