oj.uz

Submission #961024

# Submission time Handle Problem Language Result Execution time Memory
961024 2024-04-11T12:07:18 Z rxlfd314 Synchronization (JOI13_synchronization) C++17
100 / 100
 341 ms 21916 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 100005;
int N, M, Q;
ari2 edges[mxN];
vt<int> adj[mxN];

int hson[mxN], szs[mxN], parent[mxN];
void dfs_szs(int i, int p) {
  parent[i] = p;
  szs[i] = 1;
  hson[i] = -1;
  for (int j : adj[i])
    if (j != p) {
      dfs_szs(j, i);
      szs[i] += szs[j];
      if (hson[i] < 0 || szs[j] > szs[hson[i]])
        hson[i] = j;
    }
}

int head[mxN], tin[mxN], tout[mxN], rev_tin[mxN], timer;
void dfs_hld(int i) {
  rev_tin[tin[i] = timer++] = i;
  if (hson[i] >= 0) {
    head[hson[i]] = head[i];
    dfs_hld(hson[i]);
  }
  for (int j : adj[i])
    if (j != hson[i] && j != parent[i]) {
      head[j] = j;
      dfs_hld(j);
    }
  tout[i] = timer-1;
}

struct ST {
  int st[mxN<<1];
  void pset(int i, int v) {
    for (st[i+=N] = v; i > 1; i >>= 1)
      st[i>>1] = st[i] + st[i^1];
  }
  int query(int l, int r) {
    int ret = 0;
    for (l += N, r += N+1; l < r; l>>=1, r>>=1) {
      if (l & 1)
        ret += st[l++];
      if (r & 1)
        ret += st[--r];
    }
    return ret;
  }
} st_cnt;

int find_highest(int i) {
  while (st_cnt.query(tin[head[i]], tin[i]) == tin[i] - tin[head[i]] + 1)
    i = parent[head[i]];
  int lo = tin[head[i]], hi = tin[i];
  while (lo < hi) {
    int mid = lo+hi+1 >> 1;
    if (st_cnt.query(mid, hi) == hi-mid+1)
      hi = mid-1;
    else
      lo = mid;
  }
  return rev_tin[lo];
}

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> M >> Q;
  FOR(i, 0, N-2) {
    auto &[a, b] = edges[i];
    cin >> a >> b;
    adj[--a].push_back(--b);
    adj[b].push_back(a);
  }
  
  dfs_szs(0, -1);
  dfs_hld(0);
  
  vt<bool> active(N-1);
  vt<int> add_parent(N, 1), add_child(N, 1);
  #ifdef DEBUG
  cout << "bruh: " << find_highest(1)+1 << '\n';
  #endif
  FOR(_, 1, M) {
    int e;
    cin >> e, e--;
    auto [a, b] = edges[e];
    if (parent[b] == a)
      swap(a, b);
    if (!active[e]) {
      int h = a;
      int new_h = find_highest(b);
      // update add_child
      add_child[new_h] += add_parent[h];
      add_child[h] = 0;
      // update add_parent
      add_parent[new_h] += add_parent[h];
      add_parent[h] = 0;
      // set edge to active
      active[e] = true;
      st_cnt.pset(tin[a], 1);
    } else {
      int h = find_highest(b);
      int new_h = a;
      // update add_child
      add_child[new_h] = add_child[h];
      // set edge to inactive
      active[e] = false;
      st_cnt.pset(tin[a], 0);
    }
    #ifdef DEBUG
    cout << "find_highest:\n";
    FOR(i, 0, N-1)
      cout << find_highest(i)+1 << '\n';
    cout << "(add_child, add_parent):\n";
    FOR(i, 0, N-1)
      cout << i+1 << ": " << add_child[i] << ' ' << add_parent[i] << '\n';
    #endif
  }
  
  while (Q--) {
    int x;
    cin >> x, x--;
    int h = find_highest(x);
    cout << add_child[h] << '\n';
  }
}

Compilation message

synchronization.cpp: In function 'int find_highest(int)':
synchronization.cpp:71:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int mid = lo+hi+1 >> 1;
      |               ~~~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4440 KB Output is correct
5 Correct 2 ms 4440 KB Output is correct
6 Correct 2 ms 4444 KB Output is correct
7 Correct 6 ms 5348 KB Output is correct
8 Correct 6 ms 5464 KB Output is correct
9 Correct 6 ms 5212 KB Output is correct
10 Correct 64 ms 13280 KB Output is correct
11 Correct 71 ms 13208 KB Output is correct
12 Correct 255 ms 21016 KB Output is correct
13 Correct 40 ms 13208 KB Output is correct
14 Correct 49 ms 12868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 17064 KB Output is correct
2 Correct 73 ms 16976 KB Output is correct
3 Correct 105 ms 20548 KB Output is correct
4 Correct 107 ms 20544 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 3 ms 4700 KB Output is correct
7 Correct 24 ms 6228 KB Output is correct
8 Correct 330 ms 21908 KB Output is correct
9 Correct 340 ms 21908 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 21752 KB Output is correct
2 Correct 193 ms 21460 KB Output is correct
3 Correct 203 ms 21588 KB Output is correct
4 Correct 190 ms 21584 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 1 ms 4568 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 8 ms 5348 KB Output is correct
7 Correct 88 ms 14192 KB Output is correct
8 Correct 341 ms 21916 KB Output is correct
9 Correct 54 ms 14536 KB Output is correct
10 Correct 81 ms 14024 KB Output is correct
11 Correct 124 ms 18260 KB Output is correct
12 Correct 118 ms 18340 KB Output is correct
13 Correct 193 ms 21704 KB Output is correct