oj.uz

Submission #998354

# Submission time Handle Problem Language Result Execution time Memory
998354 2024-06-13T17:29:02 Z fuad27 Synchronization (JOI13_synchronization) C++17
100 / 100
 362 ms 26592 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 () {
  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 13148 KB Output is correct
2 Correct 1 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 13148 KB Output is correct
6 Correct 2 ms 13148 KB Output is correct
7 Correct 12 ms 13788 KB Output is correct
8 Correct 12 ms 13652 KB Output is correct
9 Correct 12 ms 13660 KB Output is correct
10 Correct 138 ms 19512 KB Output is correct
11 Correct 132 ms 19536 KB Output is correct
12 Correct 198 ms 25936 KB Output is correct
13 Correct 91 ms 19476 KB Output is correct
14 Correct 97 ms 18868 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 22612 KB Output is correct
2 Correct 98 ms 22356 KB Output is correct
3 Correct 99 ms 25032 KB Output is correct
4 Correct 96 ms 25172 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 13148 KB Output is correct
3 Correct 2 ms 13148 KB Output is correct
4 Correct 2 ms 12980 KB Output is correct
5 Correct 2 ms 13000 KB Output is correct
6 Correct 4 ms 13148 KB Output is correct
7 Correct 28 ms 14424 KB Output is correct
8 Correct 362 ms 26592 KB Output is correct
9 Correct 347 ms 26452 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 26452 KB Output is correct
2 Correct 318 ms 26192 KB Output is correct
3 Correct 262 ms 26196 KB Output is correct
4 Correct 261 ms 26196 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 13148 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 4 ms 13148 KB Output is correct
6 Correct 27 ms 13880 KB Output is correct
7 Correct 285 ms 20308 KB Output is correct
8 Correct 343 ms 26452 KB Output is correct
9 Correct 229 ms 20708 KB Output is correct
10 Correct 227 ms 20308 KB Output is correct
11 Correct 217 ms 23632 KB Output is correct
12 Correct 232 ms 23636 KB Output is correct
13 Correct 251 ms 26260 KB Output is correct