#include <bits/stdc++.h>
// #pragma GCC optimize ("Ofast,unroll-loops")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<int, int> pp;
#define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl
#define per(i,r,l) for(int i = (r); i >= (l); i--)
#define rep(i,l,r) for(int i = (l); i < (r); i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ss second
#define ff first
void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = 1e9 + 7, maxn = 1e5 + 5, lg = 21, inf = ll(1e9) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}
vector<int> adj[maxn];
int par[maxn], cnt[maxn];
vector<pp> his;
int get(int x){ return par[x] == -1? x: get(par[x]); }
bool unite(int u, int v){
u = get(u), v = get(v);
if(u == v) return his.pb({-1, -1}), false;
if(cnt[u] < cnt[v]) swap(u, v);
par[v] = u, cnt[u] += cnt[v];
return his.pb({v, u}), true;
}
void undo(){
auto[v, u] = his.back(); his.pop_back();
if(u + 1) par[v] = -1, cnt[u] -= cnt[v];
}
pp edge[maxn];
bool cut_edge[maxn];
void slv(int l, int r){
if(l + 1 == r) {
cut_edge[l] = get(edge[l].ff) != get(edge[l].ss);
return;
}
int mid = (l + r)>>1;
rep(i,mid,r) unite(edge[i].ff, edge[i].ss);
slv(l, mid);
rep(i,mid,r) undo();
rep(i,l,mid) unite(edge[i].ff, edge[i].ss);
slv(mid, r);
rep(i,l,mid) undo();
}
vector<int> adj2[maxn];
int st[maxn];
map<pp, bool> is;
void add_query(int u, int v){
st[u]++, st[v]--;
}
void dfs(int r, int p){
for(int c: adj2[r]) if(c - p){
dfs(c, r);
st[r] += st[c];
}
if(st[r]){
if(st[r] > 0) is[{r, p}] = true;
else is[{p, r}] = true;
}
}
int main(){
cin.tie(0) -> sync_with_stdio(0);
int n, m; cin >> n >> m;
fill(par, par + n, -1);
fill(cnt, cnt + n, 1);
rep(i,0,m){
cin >> edge[i].ff >> edge[i].ss; edge[i].ff--, edge[i].ss--;
}
slv(0, m);
rep(i,0,m) if(!cut_edge[i]) unite(edge[i].ff, edge[i].ss);
vector<int> grp(n, -1); int id = 0;
rep(i,0,n){
if(grp[get(i)] == -1) grp[get(i)] = id++;
grp[i] = grp[get(i)];
}
rep(i,0,m) if(cut_edge[i]) {
adj2[grp[edge[i].ff]].pb(grp[edge[i].ss]);
adj2[grp[edge[i].ss]].pb(grp[edge[i].ff]);
}
int q; cin >> q;
while(q--){
int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];
add_query(u, v);
}
dfs(0, 0);
vector<int> ans(m);
rep(i,0,m){
if(cut_edge[i]){
if(is.count({grp[edge[i].ff], grp[edge[i].ss]})) ans[i] = 1;
else if(is.count({grp[edge[i].ss], grp[edge[i].ff]})) ans[i] = 2;
}
}
for(int c: ans) cout << (c?(c&1?'R':'L'):'B');
return 0;
}
Compilation message
oneway.cpp: In function 'int main()':
oneway.cpp:94:38: warning: operation on 'u' may be undefined [-Wsequence-point]
94 | int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];
oneway.cpp:94:52: warning: operation on 'v' may be undefined [-Wsequence-point]
94 | int u, v; cin >> u >> v; u = grp[--u], v = grp[--v];
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
