Submission #1187700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187700		zNatsumi	Synchronization (JOI13_synchronization)	C++20	40 / 100	8093 ms	24264 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

const int N = 2e5 + 5;

int n, m, q, res = 0;
bool status[N];
vector<ii> ad[N];
vector<ii> open[N];

void dfs(int u, int p, int ed){
  res += 1;
  for(auto [v, w] : ad[u]) if(v != p){
    auto it = upper_bound(open[w].begin(), open[w].end(), make_pair(ed, m)) - open[w].begin() - 1;
    if(it == -1) continue;

    dfs(v, u, min(ed, open[w][it].second));
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m >> q;
  for(int i = 1; i < n; i++){
    int u, v; cin >> u >> v;
    ad[u].push_back({v, i});
    ad[v].push_back({u, i});
  }
  for(int i = 1; i <= m; i++){
    int d; cin >> d;
    status[d] ^= 1;
    if(status[d]) open[d].push_back({i, -1});
    else open[d].back().second = i - 1;
  }
  for(int i = 1; i < n; i++) if(status[i]) open[i].back().second = m;

  for(int i = 1; i < n; i++){
    cerr << i << "\n";
    for(auto [l, r] : open[i]) cerr << l << " " << r << "\n";
    cerr << "\n";
  }

  while(q--){
    int c; cin >> c;
    res = 0;
    dfs(c, -1, m);
    cout << res << "\n";
  }

  return 0;
}

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