제출 #38256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38256		funcsr	동기화 (JOI13_synchronization)	C++14	60 / 100	993 ms	20428 KiB

synchronization

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define _1 first
#define _2 second
#define INF 1000001919
int N, M, Q;
vector<P> G[100000];
int evt[200000];
int start[100000];
vector<P> T[100000];
int QV[100000];

int dfs(int x, int p, int time) {
  // cout<<"x="<<x<<" is counted, time="<<time<<"\n";
  int s = 1;
  for (P pp : G[x]) if (pp._1 != p) {
    int t = pp._1, e = pp._2;
    auto it = lower_bound(all(T[e]), P(time, -1));
    if (it == T[e].end()) continue;
    s += dfs(t, x, max(it->_2, time));
  }
  return s;
}

int ans[100000];
vector<int> f() {
  vector<bool> used(N-1, false);
  vector<int> ret(N, 1);
  set<int> zeros;
  zeros.insert(-1);
  rep(i, N-1) zeros.insert(i);
  rep(t, M) {
    int e = evt[t];
    if (used[e]) {
      zeros.insert(e);
      used[e] = false;
    }
    else {
      int dest = *(--zeros.find(e))+1;
      ret[dest] += ret[e+1];
      ret[e+1] = 0;
      zeros.erase(e);
      used[e] = true;
    }
  }
  return ret;
}
void solve_linear() {
  rep(i, N-1) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    if (u != i || v != i+1) abort();
  }
  rep(i, M) cin >> evt[i], evt[i]--;
  vector<int> A = f();
  int d = 1;
  rep(i, N) {
    d += A[i]-1;
    ans[i] += d;
  }

  // reverse
  rep(i, M) evt[i] = N-2-evt[i];
  vector<int> B = f();
  reverse(all(B));
  d = 1;
  for (int i=N-1; i>=0; i--) {
    d += B[i]-1;
    ans[i] += d;
  }
  rep(i, N) ans[i]--;

  rep(i, Q) {
    int x;
    cin >> x;
    x--;
    cout << ans[x] << "\n";
  }
}

int main() {
  cin >> N >> M >> Q;
  if (Q == 1) {
    rep(i, N-1) {
      int u, v;
      cin >> u >> v;
      u--, v--;
      G[u].pb(P(v, i));
      G[v].pb(P(u, i));
    }
    rep(i, N-1) start[i] = 0;
    rep(i, M) {
      cin >> evt[i];
      evt[i]--;
      start[evt[i]] ^= 1;
    }
    rep(i, Q) cin >> QV[i], QV[i]--;
    rep(i, N-1) {
      if (start[i]) start[i] = -1;
      else start[i] = INF;
    }
    reverse(evt, evt+M);
    rep(t, M) {
      int e = evt[t];
      if (start[e] == INF) {
        // open
        start[e] = t;
      }
      else {
        // close
        T[e].pb(P(t, start[e]));
        //cout<<"T["<<e<<"]: ["<<start[e]<<","<<t<<"]\n";
        start[e] = INF;
      }
    }
    cout << dfs(QV[0], -1, 0) << "\n";
  }
  else {
    solve_linear();
  }
  return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 0 / 40