oj.uz

Submission #411766

# Submission time Handle Problem Language Result Execution time Memory
411766 2021-05-25T20:52:48 Z pauloamed Synchronization (JOI13_synchronization) C++14
0 / 100
 458 ms 26036 KB 
#include<bits/stdc++.h>
using namespace std;

#define MAXN 100010
#define MAXLOG 20

int currTime;
int inTime[MAXN], outTime[MAXN], depth[MAXN];
vector<int> v[MAXN]; // adj list

int st[MAXN][MAXLOG]; // sparse table (x,i) guardando ancestral de ordem 2^i de x

void init_dfs(int x, int par){
  inTime[x] = currTime++;
  st[x][0] = par; // o ancestral de ordem 2^0 (1) de x eh o pai dele
  // se tiver pai valido (!= raiz), a prof aumenta em 1
  if(par != x) depth[x] = depth[par] + 1;

  for(int i = 0; i < v[x].size(); ++i){
    if(v[x][i] != par) init_dfs(v[x][i], x); // passo recursivo
  }
  outTime[x] = currTime++;
}


void init_st(){
  // processo cada nivel de cada vertice
  for(int x = 1; x < MAXLOG; ++x) // 2^0 ja foi calculado, calculo pro resto
  for(int i = 0; i < MAXN; ++i){ // pra cada vertice
    // olho o ancestral 2^(i-1) do meu 2^(i-1), achando entao o meu 2^i
    // if(st[i][x-1] == -1) st[i][x] = -1;
    st[i][x] = st[st[i][x-1]][x-1];
  }
}


void init(int root, int n){ // funcao init, raiz e #nos
  // botando que o pai da raiz eh -1, pode ser ela mesma tbm
  init_dfs(root, root); // calcular os ancestrais imediatos
  init_st(); // init da sparse table
}

int bit[MAXN];
int query( int index ){
    int ans(0); // acumulado
    index++; // bit eh 1-indexada, tem q ser feito se index for 0-indexado
    while(index > 0){ // enquanto posso ir pra esquerda
        ans += bit[index]; // atualizando o acumulado
        index -= index & (-index); // indo pro irmao a esquerda
    }
    return ans; // ret acumulado
}

void update( int index, int val ){
    index++; // bit eh 1-indexada
    while(index <= MAXN){ // enquanto eu puder subir na BIT
        bit[index] += val; // atualizando valores dos ancestrais
        index += index & (-index); // subindo pro pai
    }
}

int getPath(int a, int b){
  // cerr << a << " " << b << endl;
  // for(int i = 0; i < 10; ++i){
  //   cout << query(i) << " " ;
  // }cout << endl;
  if(inTime[a] > inTime[b]) swap(a, b);
  return query(inTime[b]) - query(inTime[a] - 1);
}

int val[MAXN], backup[MAXN];
int getRoot(int x){
  for(int i = MAXLOG - 1; i >= 0; --i){
    int next = st[x][i];
    int dist = (1 << i);
    // cerr << x << " " << next << " " << getPath(x, next) << endl;
    if(getPath(x, next) == dist){
      x = next;
    }
  }
  return x;
}


void addEdge(int a, int b){
  if(depth[a] > depth[b]) swap(a, b);
  // A EH PAI DE B
  update(inTime[b], 1);
  update(outTime[b], -1);
  val[getRoot(a)] += val[b] - backup[b];
}

void rmEdge(int a, int b){
  if(depth[a] > depth[b]) swap(a, b);
  // A EH PAI DE B
  update(inTime[b], -1);
  update(outTime[b], +1);
  val[b] = val[getRoot(a)];
  backup[b] = val[b];
}


int32_t main(){
  ios::sync_with_stdio(false);
  int n, m, q; cin >> n >> m >> q;

  vector<pair<int,int>> edges;
  for(int i = 1; i <= n; ++i) val[i] = 1;
  for(int i = 1; i < n; ++i){
    int a, b; cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);

    edges.push_back({a, b});
  }
  init(1, n);

  vector<bool> edgeStatus(edges.size());
  while(m--){
    int x; cin >> x; x--;
    auto e = edges[x];
    if(edgeStatus[x]) rmEdge(e.first, e.second);
    else addEdge(e.first, e.second);
    edgeStatus[x] = !edgeStatus[x];


    // cout << "=============\n";
    // for(int i = 1; i <= n; ++i){
    //   cout << i << " " << getRoot(i) << " " << val[i] << endl;
    // }
  }


  while(q--){
    int x; cin >> x;
    x = getRoot(x);
    cout << val[x] << "\n";
  }
}

Compilation message

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 10516 KB Output is correct
2 Correct 21 ms 10520 KB Output is correct
3 Incorrect 19 ms 10444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 21816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 10596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 458 ms 26036 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10444 KB Output is correct
2 Correct 18 ms 10524 KB Output is correct
3 Incorrect 17 ms 10444 KB Output isn't correct
4 Halted 0 ms 0 KB -