oj.uz

Submission #120350

# Submission time Handle Problem Language Result Execution time Memory
120350 2019-06-24T08:44:26 Z IOrtroiii Synchronization (JOI13_synchronization) C++14
100 / 100
 1540 ms 24240 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 3 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 7 ms 2944 KB Output is correct
7 Correct 50 ms 4352 KB Output is correct
8 Correct 52 ms 4352 KB Output is correct
9 Correct 52 ms 4404 KB Output is correct
10 Correct 1183 ms 18780 KB Output is correct
11 Correct 1214 ms 18776 KB Output is correct
12 Correct 1497 ms 23416 KB Output is correct
13 Correct 437 ms 18428 KB Output is correct
14 Correct 618 ms 17784 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 304 ms 20592 KB Output is correct
2 Correct 294 ms 20344 KB Output is correct
3 Correct 418 ms 22528 KB Output is correct
4 Correct 417 ms 22464 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 5 ms 2816 KB Output is correct
5 Correct 4 ms 2816 KB Output is correct
6 Correct 8 ms 2944 KB Output is correct
7 Correct 77 ms 4896 KB Output is correct
8 Correct 1425 ms 24108 KB Output is correct
9 Correct 1540 ms 24240 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1352 ms 24196 KB Output is correct
2 Correct 433 ms 23544 KB Output is correct
3 Correct 433 ms 23628 KB Output is correct
4 Correct 433 ms 23672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 4 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2816 KB Output is correct
5 Correct 7 ms 2944 KB Output is correct
6 Correct 55 ms 4432 KB Output is correct
7 Correct 1169 ms 19576 KB Output is correct
8 Correct 1337 ms 24108 KB Output is correct
9 Correct 399 ms 19440 KB Output is correct
10 Correct 666 ms 19020 KB Output is correct
11 Correct 325 ms 21736 KB Output is correct
12 Correct 485 ms 21848 KB Output is correct
13 Correct 462 ms 23668 KB Output is correct