Submission #120350

#	Time	Username	Problem	Language	Result	Execution time	Memory
120350		IOrtroiii	Synchronization (JOI13_synchronization)	C++14	100 / 100	1540 ms	24240 KiB

synchronization

#include <bits/stdc++.h>

using namespace std;

const int N = 100100;

int n, m, q;
vector<int> g[N];
int dep[N], par[17][N];
int tin[N], tout[N], tt;

void dfs(int v) {
   tin[v] = ++tt;
   for (int i = 1; i < 17; ++i) {
      par[i][v] = par[i - 1][par[i - 1][v]];
   }
   for (int u : g[v]) {
      if (u != par[0][v]) {
         dep[u] = dep[v] + 1;
         par[0][u] = v;
         dfs(u);
      }
   }
   tout[v] = tt;
}

int T[N << 2];

#define mid ((l + r) >> 1)
void add(int v, int l, int r, int L, int R, int val) {
   if (L <= l && r <= R) {
      T[v] += val;
      return;
   }
   if (L <= mid) add(v << 1, l, mid, L, R, val);
   if (mid < R) add(v << 1 | 1, mid + 1, r, L, R, val);
}

int get(int v, int l, int r, int p) {
   if (l == r) { return T[v]; }
   int ans = T[v];
   if (p <= mid) ans += get(v << 1, l, mid, p);
   else ans += get(v << 1 | 1, mid + 1, r, p);
   return ans;
}
#undef mid

int go(int v) {
   for (int i = 16; i >= 0; --i) {
      int u = par[i][v];
      if (get(1, 1, n, tin[u]) - dep[u] == get(1, 1, n, tin[v]) - dep[v]) {
         v = u;
      }
   }
   return v;
}

int ans[N];
int last[N];
bool state[N];
pair<int, int> edges[N];

int main() {
   scanf("%d %d %d", &n, &m, &q);
   for (int i = 1; i < n; ++i) {
      int v, u;
      scanf("%d %d", &v, &u);
      g[v].push_back(u);
      g[u].push_back(v);
      edges[i] = {v, u};
   }
   par[0][1] = 1;
   dfs(1);
   for (int i = 1; i < n; ++i) {
      int v, u;
      tie(v, u) = edges[i];
      if (dep[v] > dep[u]) {
         swap(v, u);
      }
      edges[i] = {v, u};
   }
   for (int i = 1; i <= n; ++i) {
      ans[i] = 1;
   }
   for (int i = 1; i <= m; ++i) {
      int id;
      scanf("%d", &id);
      int v, u;
      tie(v, u) = edges[id];
      if (!state[id]) {
         ans[go(v)] += ans[u] - last[u];
         add(1, 1, n, tin[u], tout[u], 1);
      } else {
         ans[u] = last[u] = ans[go(u)];
         add(1, 1, n, tin[u], tout[u], -1);
      }
      state[id] ^= 1;
   }
   for (int i = 1; i <= n; ++i) {
      ans[i] = ans[go(i)];
   }
   while (q--) {
      int v;
      scanf("%d", &v);
      printf("%d\n", ans[v]);
   }
}

Compilation message (stderr)

synchronization.cpp: In function 'int main()':
synchronization.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d", &n, &m, &q);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
synchronization.cpp:67:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d", &v, &u);
       ~~~~~^~~~~~~~~~~~~~~~~
synchronization.cpp:87:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &id);
       ~~~~~^~~~~~~~~~~
synchronization.cpp:104:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &v);
       ~~~~~^~~~~~~~~~

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