oj.uz

Submission #1082121

# Submission time Handle Problem Language Result Execution time Memory
1082121 2024-08-30T17:45:08 Z VinhLuu Inside information (BOI21_servers) C++17
80 / 100
 3500 ms 64620 KB 
#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 = 3e5 + 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);
    st[i] = st[i << 1] + st[i << 1|1];
  }

  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 = g[1].fin(u), val = f[0].get(1, 1, n, in[u], in[u]);
  if(v != 1 && key[1][pa[v]] != h[v]){
    if(key[1][pa[v]] < h[v]) f[1].update(1, 1, n, in[pa[v]], in[pa[v]], val);
    int dr = lower_bound(all(vr[pa[v]]), h[v]) - vr[pa[v]].begin();
    b[pa[v]][dr] += val; // add
  }
  if(u == v) return;
  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 lc(int u,int v){
  int kq = u;
  if(u == v) return kq;
  for(int i = 20; i >= 0; i --) if(v != dp[u][i] && kt(v, dp[u][i])){
    kq = dp[u][i];
    u = dp[u][i];
  }
  return kq;
}

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

int solve(int u,int tmp){
  int ans = 1;
  for(int i = 0; i < vr[u].size(); i ++) ans += b[u][i];
  if(h[key[0][u]] <= tmp && key[0][u]) ans += f[0].get(1, 1, n, in[key[0][u]], in[key[0][u]]);
  if(u == 1) return ans;

  int v = g[0].fin(u); if(h[v] <= tmp) v = pa[v];
  if(u == v) return ans;
  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];
    ans++;
    if(h[key[0][pa[u]]] <= tmp && key[1][pa[u]] > h[u]) ans += f[0].get(1, 1, n, in[key[0][pa[u]]], in[key[0][pa[u]]]);

  }else{
    ans += f[1].get(1, 1, n, in[pa[u]], in[pa[u]]);
  }
  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(h[key[0][j]] <= tmp && 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){

      int x = X[i], y = Y[i];
      if(in[x] > in[y]) swap(x, y);
      if(x == y){
        cout << "yes\n";
        continue;
      }
      if(pa[y] == x){
        if(h[y] <= i) cout << "yes\n";
        else cout << "no\n";
        continue;
      }
      cout << (query(Y[i], X[i], i) == 1 ? "yes\n" : "no\n");
    }else {
      cout << solve(X[i], i) << "\n";
    }
  }
}

Compilation message

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

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24156 KB Output is correct
2 Correct 51 ms 25680 KB Output is correct
3 Correct 49 ms 25768 KB Output is correct
4 Correct 52 ms 25872 KB Output is correct
5 Correct 45 ms 25940 KB Output is correct
6 Correct 51 ms 25556 KB Output is correct

Subtask #2
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24156 KB Output is correct
2 Correct 51 ms 25680 KB Output is correct
3 Correct 49 ms 25768 KB Output is correct
4 Correct 52 ms 25872 KB Output is correct
5 Correct 45 ms 25940 KB Output is correct
6 Correct 51 ms 25556 KB Output is correct
7 Correct 37 ms 24232 KB Output is correct
8 Correct 48 ms 25264 KB Output is correct
9 Correct 50 ms 25424 KB Output is correct
10 Correct 50 ms 25464 KB Output is correct
11 Correct 50 ms 25664 KB Output is correct
12 Correct 97 ms 25400 KB Output is correct

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24400 KB Output is correct
2 Correct 245 ms 53044 KB Output is correct
3 Correct 224 ms 53716 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24400 KB Output is correct
2 Correct 245 ms 53044 KB Output is correct
3 Correct 224 ms 53716 KB Output is correct
4 Correct 37 ms 24156 KB Output is correct
5 Correct 700 ms 53300 KB Output is correct
6 Execution timed out 3533 ms 52276 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24148 KB Output is correct
2 Correct 181 ms 63828 KB Output is correct
3 Correct 177 ms 64620 KB Output is correct
4 Correct 187 ms 64336 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 24148 KB Output is correct
2 Correct 181 ms 63828 KB Output is correct
3 Correct 177 ms 64620 KB Output is correct
4 Correct 187 ms 64336 KB Output is correct
5 Correct 30 ms 24144 KB Output is correct
6 Correct 183 ms 63828 KB Output is correct
7 Correct 172 ms 63828 KB Output is correct
8 Correct 182 ms 63312 KB Output is correct
9 Correct 185 ms 63312 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24152 KB Output is correct
2 Correct 288 ms 55636 KB Output is correct
3 Correct 221 ms 56140 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 24152 KB Output is correct
2 Correct 288 ms 55636 KB Output is correct
3 Correct 221 ms 56140 KB Output is correct
4 Correct 35 ms 24224 KB Output is correct
5 Correct 312 ms 55636 KB Output is correct
6 Correct 223 ms 55632 KB Output is correct

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24344 KB Output is correct
2 Correct 182 ms 63952 KB Output is correct
3 Correct 180 ms 64188 KB Output is correct
4 Correct 187 ms 64340 KB Output is correct
5 Correct 35 ms 24152 KB Output is correct
6 Correct 283 ms 55836 KB Output is correct
7 Correct 222 ms 56144 KB Output is correct
8 Correct 257 ms 55104 KB Output is correct
9 Correct 261 ms 55120 KB Output is correct
10 Correct 217 ms 61008 KB Output is correct
11 Correct 242 ms 59984 KB Output is correct

Subtask #10
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 32 ms 24344 KB Output is correct
2 Correct 182 ms 63952 KB Output is correct
3 Correct 180 ms 64188 KB Output is correct
4 Correct 187 ms 64340 KB Output is correct
5 Correct 35 ms 24152 KB Output is correct
6 Correct 283 ms 55836 KB Output is correct
7 Correct 222 ms 56144 KB Output is correct
8 Correct 257 ms 55104 KB Output is correct
9 Correct 261 ms 55120 KB Output is correct
10 Correct 217 ms 61008 KB Output is correct
11 Correct 242 ms 59984 KB Output is correct
12 Correct 30 ms 24152 KB Output is correct
13 Correct 184 ms 63816 KB Output is correct
14 Correct 172 ms 63824 KB Output is correct
15 Correct 203 ms 63340 KB Output is correct
16 Correct 187 ms 63296 KB Output is correct
17 Correct 35 ms 24156 KB Output is correct
18 Correct 303 ms 55632 KB Output is correct
19 Correct 220 ms 55636 KB Output is correct
20 Correct 265 ms 54612 KB Output is correct
21 Correct 261 ms 54608 KB Output is correct
22 Correct 201 ms 59040 KB Output is correct
23 Correct 273 ms 61572 KB Output is correct
24 Correct 234 ms 61280 KB Output is correct

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24328 KB Output is correct
2 Correct 49 ms 25684 KB Output is correct
3 Correct 48 ms 25680 KB Output is correct
4 Correct 53 ms 25940 KB Output is correct
5 Correct 44 ms 25936 KB Output is correct
6 Correct 48 ms 25680 KB Output is correct
7 Correct 36 ms 24400 KB Output is correct
8 Correct 223 ms 53192 KB Output is correct
9 Correct 204 ms 53328 KB Output is correct
10 Correct 30 ms 24408 KB Output is correct
11 Correct 170 ms 64172 KB Output is correct
12 Correct 176 ms 64244 KB Output is correct
13 Correct 182 ms 64340 KB Output is correct
14 Correct 37 ms 24156 KB Output is correct
15 Correct 277 ms 55944 KB Output is correct
16 Correct 212 ms 56140 KB Output is correct
17 Correct 252 ms 54948 KB Output is correct
18 Correct 271 ms 55132 KB Output is correct
19 Correct 213 ms 61008 KB Output is correct
20 Correct 247 ms 59840 KB Output is correct
21 Correct 208 ms 53676 KB Output is correct
22 Correct 202 ms 53944 KB Output is correct
23 Correct 225 ms 54092 KB Output is correct
24 Correct 228 ms 54376 KB Output is correct
25 Correct 215 ms 56268 KB Output is correct
26 Correct 202 ms 54100 KB Output is correct
27 Correct 174 ms 54100 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 24328 KB Output is correct
2 Correct 49 ms 25684 KB Output is correct
3 Correct 48 ms 25680 KB Output is correct
4 Correct 53 ms 25940 KB Output is correct
5 Correct 44 ms 25936 KB Output is correct
6 Correct 48 ms 25680 KB Output is correct
7 Correct 36 ms 24400 KB Output is correct
8 Correct 223 ms 53192 KB Output is correct
9 Correct 204 ms 53328 KB Output is correct
10 Correct 30 ms 24408 KB Output is correct
11 Correct 170 ms 64172 KB Output is correct
12 Correct 176 ms 64244 KB Output is correct
13 Correct 182 ms 64340 KB Output is correct
14 Correct 37 ms 24156 KB Output is correct
15 Correct 277 ms 55944 KB Output is correct
16 Correct 212 ms 56140 KB Output is correct
17 Correct 252 ms 54948 KB Output is correct
18 Correct 271 ms 55132 KB Output is correct
19 Correct 213 ms 61008 KB Output is correct
20 Correct 247 ms 59840 KB Output is correct
21 Correct 208 ms 53676 KB Output is correct
22 Correct 202 ms 53944 KB Output is correct
23 Correct 225 ms 54092 KB Output is correct
24 Correct 228 ms 54376 KB Output is correct
25 Correct 215 ms 56268 KB Output is correct
26 Correct 202 ms 54100 KB Output is correct
27 Correct 174 ms 54100 KB Output is correct
28 Correct 34 ms 24148 KB Output is correct
29 Correct 49 ms 25428 KB Output is correct
30 Correct 48 ms 25396 KB Output is correct
31 Correct 46 ms 25428 KB Output is correct
32 Correct 52 ms 25704 KB Output is correct
33 Correct 115 ms 25428 KB Output is correct
34 Correct 36 ms 24152 KB Output is correct
35 Correct 677 ms 53368 KB Output is correct
36 Execution timed out 3553 ms 52164 KB Time limit exceeded
37 Halted 0 ms 0 KB -