Submission #1081719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081719		VinhLuu	Inside information (BOI21_servers)	C++17	0 / 100	33 ms	32604 KiB

servers

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
#define all(lmao) lmao.begin(), lmao.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 2e9;

struct IT {
  int st[N << 2], lz[N << 2];
  void dolz(int i,int l,int r){
    if(!lz[i]) return;
    int x = lz[i], mid = (l + r) / 2; lz[i] = 0;
    st[i << 1] += x * (mid - l + 1), st[i << 1|1] += x * (r - mid);
    lz[i << 1] += x, lz[i << 1|1] += x;
  }

  void update(int i,int l,int r,int u,int v,int x){
    if(l > r || r < u || v < l) return;
    if(u <= l && r <= v){
      st[i] += x * (r - l + 1);
      lz[i] += x;
      return;
    }
    dolz(i, l, r);
    int mid = (l + r) / 2;
    update(i << 1, l, mid, u, v, x);
    update(i << 1|1, mid + 1, r, u, v, x);
  }

  int get(int i,int l,int r,int u,int v){
    if(l > r || r < u || v < l) return 0;
    if(u <= l && r <= v) return st[i];
    dolz(i, l, r);
    int mid = (l + r) / 2;
    return get(i << 1, l, mid, u, v) + get(i << 1|1, mid + 1, r, u, v);
  }
} f[2];

struct DSU{
  int par[N];

  void re(int n){
    for(int i = 1; i <= n; i ++) par[i] = i;
  }
  int fin(int u){
    return par[u] == u ? u : par[u] = fin(par[u]);
  }
  void dsu(int u,int v){
    u = fin(u);
    v = fin(v);
    if(u == v) return;
    par[u] = v;
  }
} g[2];

int n, q, T[N], X[N], Y[N], in[N], demin, en[N], head[N], pa[N], dp[N][22], d[N], be[N], h[N], key[2][N], tn[N];
vector<pii> p[N];

bool kt(int u,int v){
  return in[u] <= in[v] && in[v] <= en[u];
}

int LCA(int u,int v){
  if(kt(u, v)) return u;
  int lca = u;
  for(int i = 20; i >= 0; i --) if(kt(dp[u][i], v)) lca = dp[u][i]; else u = dp[u][i];
  return lca;
}

void dfs(int u,int v){

  d[u] = 1;
  for(auto [j, w] : p[u]) if(j != v){
    dfs(j, u);
    d[u] += d[j];
    pa[j] = u;
    h[j] = w;
  }

}

int scc = 1;

vector<int> vr[N], b[N];

void hld(int u,int v){
  in[u] = ++demin;
  if(!head[scc]) head[scc] = u;
  be[u] = scc;
  tn[demin] = u;
  if(!v){
      for(int i = 0; i <= 20; i ++) dp[u][i] = u;
  }else{
    dp[u][0] = v;
    for(int i = 1; i <= 20; i ++) dp[u][i] = dp[dp[u][i - 1]][i - 1];
  }

  int mx = 0, val = 0;
  for(auto [j, w] : p[u]) if(j != v && d[j] > d[mx]) val = w, mx = j;

  key[0][u] = mx, key[1][u] = val;

  if(mx) hld(mx, u);

  for(auto [j, w] : p[u]) if(j != v && j != mx){
    scc++;
    vr[u].pb(w);
    hld(j, u);
  }

  sort(all(vr[u]));
  for(auto j : vr[u]) b[u].pb(0);

  en[u] = demin;
}

void up(int u,int tmp){

  if(h[pa[u]] <= tmp){
    if(pa[u] == 1){
      g[0].dsu(u, pa[u]);
      g[1].dsu(u, pa[u]);
    }else{
      if(h[pa[u]] > h[u]) g[0].dsu(u, pa[u]);
      else g[1].dsu(u, pa[u]);
    }
    for(auto [j, w] : p[u]) if(j != pa[u]){
      if(w > h[u] && w <= tmp) g[1].dsu(j, u);
      if(w < h[u] && w <= tmp) g[0].dsu(j, u);
    }
  }
  int v = pa[g[1].fin(u)], val = f[0].get(1, 1, n, in[u], in[u]);
  if(key[0][pa[u]] != u){
    int dr = lower_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin();
    b[pa[u]][dr] += val; // add
    if(key[1][pa[u]] < h[u]) f[1].update(1, 1, n, in[pa[u]], in[pa[u]], val);
  }
  u = pa[u];
  while(true){
    if(be[u] == be[v]){
      f[0].update(1, 1, n, in[v], in[u], val);
      return;
    }
    int j = pa[head[be[u]]];
    if(h[head[be[u]]] > key[1][tn[in[j]]]) f[1].update(1, 1, n, in[j], in[j], val);
    int dr = lower_bound(all(vr[j]), h[head[be[u]]]) - vr[j].begin();
    b[j][dr] += val; // add
    f[0].update(1, 1, n, in[head[be[u]]], in[u], val);
    u = j;
  }
}

int query(int u,int v){
  int lca = LCA(u, v);
  int fu = g[0].fin(u), fv = g[1].fin(v);
  if(kt(fu, lca) && kt(fv, lca)) return 1;
  return 0;
}

int solve(int u){
  int ans = f[0].get(1, 1, n, in[u], in[u]);

  if(u == 1) return ans;

  int v = pa[g[0].fin(u)];
//  cerr << v << " " << ans << " f\n";
  if(key[0][pa[u]] != u){
    int dr = upper_bound(all(vr[pa[u]]), h[u]) - vr[pa[u]].begin();
    for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i];
//    cerr << ans << " d\n";
    ans++;
    if(key[1][pa[u]] > h[u]) ans += f[0].get(1, 1, n, in[key[0][pa[u]]], in[key[0][pa[u]]]);
    cerr << f[0].get(1, 1, n, in[key[0][pa[u]]], in[key[0][pa[u]]]) << "t\n";
  }else{
    ans += f[1].get(1, 1, n, in[pa[u]], in[pa[u]]);
//    cerr << f[1].get(1, 1, n, in[pa[u]], in[pa[u]]) << " g\n";
  }
  u = pa[u];

  while(true){
    if(be[u] == be[v]){
      if(u == v) return ans;
      ans += f[1].get(1, 1, n, in[v], in[u] - 1);
      return ans;
    }
    int j = pa[head[be[u]]];
//    cerr << j << " t\n";
    int k = head[be[u]];
    int pos = upper_bound(all(vr[j]), h[k]) - vr[j].begin();
    for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i];
    ans += f[1].get(1, 1, n, in[k], in[u] - 1);
    ans++;
    if(key[1][j] > h[k]) ans += f[0].get(1, 1, n, in[key[0][j]], in[key[0][j]]);
    u = j;
  }
  return ans;
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }

  cin >> n >> q;
  q = n + q - 1;
  g[1].re(n), g[0].re(n);
  for(int i = 1; i <= q; i ++){
    char c; cin >> c;
    if(c == 'S'){
      cin >> X[i] >> Y[i];
      T[i] = 0,
      p[X[i]].pb({Y[i], i});
      p[Y[i]].pb({X[i], i});
    }else if(c == 'Q'){
      T[i] = 1;
      cin >> X[i] >> Y[i];
    }else{
      T[i] = 2;
      cin >> X[i];
    }
  }

  pa[1] = 1;
  h[1] = 0;
  dfs(1, 0);
  hld(1, 0);

  for(int i = 1; i <= n; i ++) f[0].update(1, 1, n, in[i], in[i], 1), f[1].update(1, 1, n, in[i], in[i], 1);

  for(int i = 1; i <= q; i ++){
    if(T[i] == 0){
      if(in[X[i]] < in[Y[i]]) swap(X[i], Y[i]);
      up(X[i], i);
    }else if(T[i] == 1){
      cout << (query(Y[i], X[i]) == 1 ? "yes\n" : "no\n");
    }else {
      cout << solve(X[i]) << "\n";
    }
  }
}

Compilation message (stderr)

servers.cpp: In function 'void hld(int, int)':
servers.cpp:120:12: warning: unused variable 'j' [-Wunused-variable]
  120 |   for(auto j : vr[u]) b[u].pb(0);
      |            ^
servers.cpp: In function 'int solve(int)':
servers.cpp:177:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |     for(int i = dr; i < vr[pa[u]].size(); i ++) ans += b[pa[u]][i];
      |                     ~~^~~~~~~~~~~~~~~~~~
servers.cpp:198:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |     for(int i = pos; i < vr[j].size(); i ++) ans += b[j][i];
      |                      ~~^~~~~~~~~~~~~~
servers.cpp: In function 'int main()':
servers.cpp:211:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
servers.cpp:212:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5