oj.uz

Submission #550214

# Submission time Handle Problem Language Result Execution time Memory
550214 2022-04-17T15:21:06 Z lorenzoferrari Inside information (BOI21_servers) C++17
50 / 100
 508 ms 65632 KB 
/*

for each server v, define f(v, t) as the number of servers
reachable from v using share operations with timestamp >= t

each node v has deg(v) "interesting" values t, its edges
\sum_{v=0}^{n}{ deg(v) } = O(n)

f(v, t) = f(v, max tt <= t s.t. tt is "interesting", or 0 if no such tt exists)

f(v, t) = 1 (me) + \sum_{u,w \in adj[v] s.t. w >= t}{ f(u, w+1) }

answer query "count how many have a": return f(a, 0)

answer query "does a have b": LCA, is path a->b strictly increasing
*/

#include <bits/stdc++.h>
using namespace std;

struct nd {
  int v, tin, tout, max;
  bool inc, dec;
  nd() {}
  nd(int v, int t = -1) : v(v), tin(t), tout(t), max(t), inc(true), dec(true) {}
};
nd join(const nd& a, const nd& b) {
  nd ans;
  ans.v = b.v;
  ans.tin = a.tin != -1 ? a.tin : b.tin;
  ans.tout = b.tout != -1 ? b.tout : a.tout;
  ans.max = max(a.max, b.max);
  ans.inc = a.inc && b.inc && (a.tin == -1 || b.tin == -1 || a.tout < b.tin);
  ans.dec = a.dec && b.dec && (a.tin == -1 || b.tin == -1 || a.tout > b.tin);
  return ans;
}

struct Lca {
  const int LOG = 18;
  int n;
  vector<int> dep;
  vector<vector<nd>> up;
  Lca(int n, vector<int> par, vector<int> dep, vector<int> tim) : n(n), dep(dep) {
    up.assign(n, vector<nd>(LOG));
    for (int i = 0; i < n; ++i) up[i][0] = nd(par[i], tim[i]);
    for (int i = 1; i < LOG; ++i) {
      for (int j = 0; j < n; ++j) {
        up[j][i] = join(up[j][i-1], up[up[j][i-1].v][i-1]);
      }
    }
  }
  nd lift(nd v, int k) {
    for (int i = LOG-1; i >= 0; --i) {
      if (k >= (1 << i)) {
        k -= (1 << i);
        v = join(v, up[v.v][i]);
      }
    }
    return v;
  }
  bool good(int a, int b, int t) {
    // return wheher path a->b is strictly increasing and with timestamp <= t
    nd na(a); na = lift(na, dep[a] - dep[b]);
    nd nb(b); nb = lift(nb, dep[b] - dep[a]);
    for (int i = LOG-1; i >= 0; --i) {
      if (up[na.v][i].v != up[nb.v][i].v) {
        na = join(na, up[na.v][i]);
        nb = join(nb, up[nb.v][i]);
      }
    }
    if (na.v != nb.v) {
      na = lift(na, 1);
      nb = lift(nb, 1);
    }
    return na.inc && nb.dec && (na.tout <= nb.tout || na.tin == -1 || nb.tin == -1) && max(na.max, nb.max) <= t;
  }
};

int main() {
#ifdef LORENZO
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  int n; cin >> n;
  int k; cin >> k;
  vector<array<int, 3>> qs;
  vector<vector<array<int, 2>>> adj(n);
  for (int i = 0; i < n-1+k; ++i) {
    char c; cin >> c;
    if (c == 'S') {
      int a, b; cin >> a >> b; --a; --b;
      adj[a].push_back({b, i});
      adj[b].push_back({a, i});
    } else if (c == 'Q') {
      int a, d; cin >> a >> d; --a; --d;
      qs.push_back({a, d, i});
    } else if (c == 'C') {
      int d; cin >> d; --d;
      qs.push_back({d, -1, i});
    }
  }
  vector<int> par(n, 0), dep(n, 0), tim(n, -1);
  auto dfs = [&](auto&& self, int v) -> void {
    for (auto& [u, t] : adj[v]) {
      if (u == par[v]) continue;
      par[u] = v;
      tim[u] = t;
      dep[u] = dep[v] + 1;
      self(self, u);
    }
  };
  dfs(dfs, 0);
  Lca lca(n, par, dep, tim);
  for (auto [a, b, t] : qs) {
    if (b != -1) {
      cout << (lca.good(b, a, t) ? "yes" : "no") << "\n";
    } else {
      cout << 42 << "\n";
    }
  }
}

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2116 KB Output is correct
2 Correct 105 ms 5264 KB Output is correct
3 Correct 91 ms 5304 KB Output is correct
4 Correct 120 ms 5292 KB Output is correct
5 Correct 108 ms 5312 KB Output is correct
6 Correct 99 ms 5312 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2116 KB Output is correct
2 Correct 105 ms 5264 KB Output is correct
3 Correct 91 ms 5304 KB Output is correct
4 Correct 120 ms 5292 KB Output is correct
5 Correct 108 ms 5312 KB Output is correct
6 Correct 99 ms 5312 KB Output is correct
7 Incorrect 72 ms 3016 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2160 KB Output is correct
2 Correct 292 ms 61720 KB Output is correct
3 Correct 282 ms 61716 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2160 KB Output is correct
2 Correct 292 ms 61720 KB Output is correct
3 Correct 282 ms 61716 KB Output is correct
4 Incorrect 76 ms 3180 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2112 KB Output is correct
2 Correct 292 ms 61800 KB Output is correct
3 Correct 326 ms 61788 KB Output is correct
4 Correct 340 ms 61724 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2112 KB Output is correct
2 Correct 292 ms 61800 KB Output is correct
3 Correct 326 ms 61788 KB Output is correct
4 Correct 340 ms 61724 KB Output is correct
5 Incorrect 69 ms 2200 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2184 KB Output is correct
2 Correct 302 ms 62172 KB Output is correct
3 Correct 313 ms 62812 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2184 KB Output is correct
2 Correct 302 ms 62172 KB Output is correct
3 Correct 313 ms 62812 KB Output is correct
4 Incorrect 75 ms 3104 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2112 KB Output is correct
2 Correct 301 ms 61784 KB Output is correct
3 Correct 299 ms 61696 KB Output is correct
4 Correct 345 ms 61708 KB Output is correct
5 Correct 79 ms 2112 KB Output is correct
6 Correct 294 ms 62208 KB Output is correct
7 Correct 293 ms 62644 KB Output is correct
8 Correct 372 ms 63040 KB Output is correct
9 Correct 322 ms 63004 KB Output is correct
10 Correct 378 ms 65632 KB Output is correct
11 Correct 462 ms 65196 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2112 KB Output is correct
2 Correct 301 ms 61784 KB Output is correct
3 Correct 299 ms 61696 KB Output is correct
4 Correct 345 ms 61708 KB Output is correct
5 Correct 79 ms 2112 KB Output is correct
6 Correct 294 ms 62208 KB Output is correct
7 Correct 293 ms 62644 KB Output is correct
8 Correct 372 ms 63040 KB Output is correct
9 Correct 322 ms 63004 KB Output is correct
10 Correct 378 ms 65632 KB Output is correct
11 Correct 462 ms 65196 KB Output is correct
12 Incorrect 67 ms 3040 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2160 KB Output is correct
2 Correct 107 ms 5256 KB Output is correct
3 Correct 98 ms 5316 KB Output is correct
4 Correct 120 ms 5484 KB Output is correct
5 Correct 103 ms 5400 KB Output is correct
6 Correct 91 ms 5368 KB Output is correct
7 Correct 71 ms 3012 KB Output is correct
8 Correct 274 ms 61788 KB Output is correct
9 Correct 273 ms 61764 KB Output is correct
10 Correct 70 ms 2968 KB Output is correct
11 Correct 311 ms 65072 KB Output is correct
12 Correct 298 ms 65104 KB Output is correct
13 Correct 370 ms 64964 KB Output is correct
14 Correct 74 ms 3000 KB Output is correct
15 Correct 303 ms 62176 KB Output is correct
16 Correct 299 ms 62732 KB Output is correct
17 Correct 357 ms 63092 KB Output is correct
18 Correct 331 ms 63120 KB Output is correct
19 Correct 371 ms 65504 KB Output is correct
20 Correct 508 ms 65448 KB Output is correct
21 Correct 303 ms 62256 KB Output is correct
22 Correct 321 ms 62364 KB Output is correct
23 Correct 326 ms 62604 KB Output is correct
24 Correct 324 ms 62900 KB Output is correct
25 Correct 374 ms 62832 KB Output is correct
26 Correct 325 ms 62176 KB Output is correct
27 Correct 280 ms 62136 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 73 ms 2160 KB Output is correct
2 Correct 107 ms 5256 KB Output is correct
3 Correct 98 ms 5316 KB Output is correct
4 Correct 120 ms 5484 KB Output is correct
5 Correct 103 ms 5400 KB Output is correct
6 Correct 91 ms 5368 KB Output is correct
7 Correct 71 ms 3012 KB Output is correct
8 Correct 274 ms 61788 KB Output is correct
9 Correct 273 ms 61764 KB Output is correct
10 Correct 70 ms 2968 KB Output is correct
11 Correct 311 ms 65072 KB Output is correct
12 Correct 298 ms 65104 KB Output is correct
13 Correct 370 ms 64964 KB Output is correct
14 Correct 74 ms 3000 KB Output is correct
15 Correct 303 ms 62176 KB Output is correct
16 Correct 299 ms 62732 KB Output is correct
17 Correct 357 ms 63092 KB Output is correct
18 Correct 331 ms 63120 KB Output is correct
19 Correct 371 ms 65504 KB Output is correct
20 Correct 508 ms 65448 KB Output is correct
21 Correct 303 ms 62256 KB Output is correct
22 Correct 321 ms 62364 KB Output is correct
23 Correct 326 ms 62604 KB Output is correct
24 Correct 324 ms 62900 KB Output is correct
25 Correct 374 ms 62832 KB Output is correct
26 Correct 325 ms 62176 KB Output is correct
27 Correct 280 ms 62136 KB Output is correct
28 Incorrect 71 ms 3036 KB Extra information in the output file
29 Halted 0 ms 0 KB -