oj.uz

Submission #998355

# Submission time Handle Problem Language Result Execution time Memory
998355 2024-06-13T17:29:27 Z fuad27 Synchronization (JOI13_synchronization) C++17
100 / 100
 219 ms 24032 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int lg = 20;
int tin[N], tout[N];
int up[N][lg];
pair<int,int> e[N];
vector<int> child[N];
int tim=0;
array<int, 2> ans[N];
int depth[N];
namespace BIT {
  int fen[N];
  void upd(int at, int val) {
    at++;
    while(at < N) {
      fen[at] += val;
      at += at&-at;
    }
  }
  int query(int at) {
    at++;
    int ret = 0;
    while(at > 0) {
      ret += fen[at];
      at -= at&-at;
    }
    return ret;
  }
};
void change(int at, int val) {
  BIT::upd(tin[at], val);
  BIT::upd(tout[at], -val);
}
int query(int anc, int ch) {
  return BIT::query(tin[ch])-BIT::query(tin[anc]);
}
void dfs(int at, int p) {
  up[at][0] = p;
  tin[at] = tim++;
  for(int i = 1;i<lg;i++) {
    up[at][i] = up[up[at][i-1]][i-1];
  }
  for(int i = 0;i<child[at].size();i++) {
    if(child[at][i] != p) {
      depth[child[at][i]] = depth[at]+1;
      dfs(child[at][i], at);
    }
  }
  tout[at] = tim;
}
int findroot(int at) {
  for(int i = lg-1;i>=0;i--) {
    if(up[at][i] == 0)continue;
    if(query(up[at][i], at) == depth[at]-depth[up[at][i]]) {
      at = up[at][i];
    }
  }
  return at;
}
int state[N];
int main () {
  cin.tie(0)->sync_with_stdio(0);
  int n, m, q;
  cin >> n >> m >> q;
  memset(up, 0, sizeof up);  
  for(int i = 1;i<n;i++) {
    cin >> e[i].first >> e[i].second;
    child[e[i].first].push_back(e[i].second);
    child[e[i].second].push_back(e[i].first);
  }
  dfs(1, 0);
  for(int i = 1;i<n;i++) {
    if(depth[e[i].first]>depth[e[i].second])swap(e[i].first, e[i].second);
  }
  for(int i = 1;i<=n;i++)ans[i][0]=1;
  for(int i = 0;i<m;i++) {
    int c;
    cin >> c;
    state[c]^=1;
    if(state[c] == 1) {
      int r = findroot(e[c].first);
      int v1 = ans[e[c].second][0]+ans[r][0]-ans[e[c].second][1];
      change(e[c].second, 1);
      ans[r][0] = v1;
    }
    else {
      int r = findroot(e[c].second);
      ans[e[c].second][1] = ans[r][0];
      ans[e[c].second][0] = ans[r][0];
      change(e[c].second, -1);
    }
  }
  while(q--) {
    int c;
    cin >> c;
    cout << ans[findroot(c)][0] << "\n";
  }
}

Compilation message

synchronization.cpp: In function 'void dfs(int, int)':
synchronization.cpp:44:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i = 0;i<child[at].size();i++) {
      |                 ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13144 KB Output is correct
2 Correct 2 ms 13148 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 2 ms 13144 KB Output is correct
6 Correct 2 ms 13244 KB Output is correct
7 Correct 13 ms 13400 KB Output is correct
8 Correct 9 ms 13404 KB Output is correct
9 Correct 8 ms 13656 KB Output is correct
10 Correct 87 ms 17220 KB Output is correct
11 Correct 85 ms 17232 KB Output is correct
12 Correct 151 ms 23528 KB Output is correct
13 Correct 51 ms 17620 KB Output is correct
14 Correct 57 ms 17224 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20572 KB Output is correct
2 Correct 54 ms 20312 KB Output is correct
3 Correct 65 ms 23384 KB Output is correct
4 Correct 66 ms 23380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13144 KB Output is correct
2 Correct 2 ms 13144 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 3 ms 13148 KB Output is correct
7 Correct 13 ms 14260 KB Output is correct
8 Correct 195 ms 23528 KB Output is correct
9 Correct 193 ms 23648 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 23628 KB Output is correct
2 Correct 104 ms 24032 KB Output is correct
3 Correct 110 ms 23980 KB Output is correct
4 Correct 104 ms 23892 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13144 KB Output is correct
2 Correct 2 ms 13172 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 13148 KB Output is correct
5 Correct 2 ms 13148 KB Output is correct
6 Correct 11 ms 13660 KB Output is correct
7 Correct 116 ms 17640 KB Output is correct
8 Correct 219 ms 23524 KB Output is correct
9 Correct 56 ms 18116 KB Output is correct
10 Correct 73 ms 18004 KB Output is correct
11 Correct 74 ms 21072 KB Output is correct
12 Correct 74 ms 21072 KB Output is correct
13 Correct 110 ms 23892 KB Output is correct