/*#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
#include<bits/stdc++.h>
typedef long long ll;
typedef long double ld;
typedef __int128 vll;
typedef long long ftyp;
typedef std::complex<ftyp> vec;
#define llll std::pair<ll , ll>
#define pb push_back
#define fi first
#define sec second
#define cx real
#define cy imag
#define all(a) a.begin() , a.end()
#define debug std::cout << "!!ALERT ALERT!!" << std::endl;
const ll limit = 1e18+7;
const ll sus = 1e5+5;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll n , m , q , o = 0;
std::vector<llll> adj[sus] , sadj[sus];
std::vector<ll> spars[22];
struct nd{
ll ti , lw;
};
std::vector<nd> v(sus);std::vector<ll> vis(sus);
ll isb[sus] , grp[sus] , ans[sus] , ttn[sus] , ntt[sus] , val[sus] , st[sus];
llll par[sus] , rp[sus];
void brig(ll crt , ll prve){
v[crt].ti = o++;
v[crt].lw = v[crt].ti;
vis[crt] = 1;
for(auto j:adj[crt]){
if(vis[j.fi] == 0){
brig(j.fi , j.sec);
if(v[j.fi].lw > v[crt].ti){
isb[j.sec] = 1;
}
}
if(j.sec != prve){
v[crt].lw = std::min(v[crt].lw , v[j.fi].lw);
}
}
}
void crnt(ll crt , ll s){
grp[crt] = s;
vis[crt] = 1;
for(auto j:adj[crt]){
if(vis[j.fi] == 0){
if(isb[j.sec]){
crnt(j.fi , o++);
}
else{
crnt(j.fi , s);
}
}
}
}
void dfs(ll crt , ll prv){
ll mt = o++;
st[crt] = spars[0].size();
spars[0].pb(mt);
ttn[mt] = crt;
ntt[crt] = mt;
for(auto j:sadj[crt]){
if(j.fi != prv){
par[j.fi] = {crt , j.sec};
dfs(j.fi , crt);
spars[0].pb(mt);
}
}
}
void callans(ll crt , ll prv){
for(auto j:sadj[crt]){
if(j.fi != prv){
callans(j.fi , crt);
val[crt] += val[j.fi];
}
}
//std::cout << crt << " " << prv << " " << val[crt] << "\n";
if(val[crt] > 0){
if(par[crt].fi != rp[par[crt].sec].sec){
ans[par[crt].sec] = 1;
}
else{
ans[par[crt].sec] = 2;
}
}
if(val[crt] < 0){
if(par[crt].fi == rp[par[crt].sec].sec){
ans[par[crt].sec] = 2;
}
else{
ans[par[crt].sec] = 1;
}
}
}
void solve(){
std::cin >> n >> m;
for(ll i = 1;m>=i;i++){
ll x , y;std::cin >> x >> y;
adj[x].pb({y , i});adj[y].pb({x , i});
rp[i] = {x , y};
}
brig(1 , -1);
fill(all(vis) , 0);
o = 2;
crnt(1 , 1);
for(ll i = 1 ; n>=i;i++){
for(auto j:adj[i]){
if(grp[j.fi] != grp[i]){
sadj[grp[i]].pb({grp[j.fi] , j.sec});
}
}
}
dfs(1 , 0);
for(ll j = 1;18>j;j++){
for(ll i = 0;i + (1ll << j)-1 < spars[j-1].size();i++){
spars[j].pb(std::min(spars[j-1][i] , spars[j-1][i+(1ll<<(j-1))]));
}
}
std::cin >> q;
while(q--){
ll x , y;std::cin >> x >> y;
x = grp[x];y = grp[y];
if(x == y){
continue;
}
ll ab = log2(x - y + 1);
ll mn = std::min(st[x] , st[y]) , mx = std::max(st[x] , st[y]);
ll k = std::min(spars[ab][st[x]] , spars[ab][mx - (1ll << ab) + 1]);
k = ttn[k];
val[x]++;
val[y]--;
}
callans(1 , 0);
for(ll i = 1;m>=i;i++){
if(ans[i] == 0){
std::cout << "B";
}
else if(ans[i] == 1){
std::cout << "R";
}
else{
std::cout << "L";
}
}
return;/**/
}
int main(){
std::ios_base::sync_with_stdio(false);std::cin.tie(NULL);
ll t = 1;
//std::cin >> t;
while(t--){
solve();
}
}
Compilation message
oneway.cpp:5:78: warning: "/*" within comment [-Wcomment]
5 | #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")/**/
|
oneway.cpp: In function 'void solve()':
oneway.cpp:121:35: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(ll i = 0;i + (1ll << j)-1 < spars[j-1].size();i++){
| ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~
oneway.cpp:133:8: warning: unused variable 'mn' [-Wunused-variable]
133 | ll mn = std::min(st[x] , st[y]) , mx = std::max(st[x] , st[y]);
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
