Submission #38203

#	Time	Username	Problem	Language	Result	Execution time	Memory
38203		funcsr	Synchronization (JOI13_synchronization)	C++14	30 / 100	223 ms	20028 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 main() {
  cin >> N >> M >> Q;
  if (Q > 1) abort();
  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";
  return 0;
}

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