제출 #961024

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961024		rxlfd314	동기화 (JOI13_synchronization)	C++17	100 / 100	341 ms	21916 KiB

synchronization

#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';
  }
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40