Submission #718630

#	Time	Username	Problem	Language	Result	Execution time	Memory
718630		ktkerem	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	4 ms	7380 KiB

oneway

/*#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 (stderr)

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]);
      |        ^~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40