oj.uz

Submission #545559

# Submission time Handle Problem Language Result Execution time Memory
545559 2022-04-04T20:42:57 Z ivan_tudor Synchronization (JOI13_synchronization) C++14
100 / 100
 505 ms 24632 KB 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int in[N], out[N];
int aib[N];
void update(int poz, int val){
  for(int i = poz; i < N; i+= i &(-i))
    aib[i]+=val;
}
int query(int poz){
  int ans = 0;
  for(int i = poz; i >0; i-= i&(-i)){
    ans+= aib[i];
  }
  return ans;
}
struct edgesstr{
  int x, y;
};
edgesstr edg[N];
vector<int> gr[N];
int par[17][N];
int inters[N];
bool activ[N];
int ans[N];

void dfs_init(int nod, int dad, int &cnt){
  par[0][nod] = dad;
  for(int log = 1; log<17; log++){
    par[log][nod] = par[log - 1][par[log - 1][nod]];
  }
  in[nod] = ++ cnt;
  for(auto x:gr[nod]){
    if(dad == x)
      continue;
    dfs_init(x, nod, cnt);
  }
  out[nod] = cnt;
}
int find_high(int nod){
  int rsp = nod;
  int tp = query(in[nod]);
  for(int p2 = 16; p2>=0; p2--){
    int sus = par[p2][rsp];
    if(sus != 0 && query(in[sus]) == tp)
      rsp = sus;
  }
  return rsp;
}
void break_edge(int id){
  int a = edg[id].x;
  int b = edg[id].y;
  if(in[a] > in[b])
    swap(a, b);
  a = find_high(a);
  inters[id] = ans[a];
  update(in[b], 1);
  update(out[b] + 1, -1);
  ans[b] = ans[a];
  activ[id] = false;
}

void join_edge(int id){
  int a = edg[id].x;
  int b = edg[id].y;
  if(in[a] > in[b])
    swap(a, b);
  a = find_high(a);
  int newval = ans[a] + ans[b] - inters[id];
  update(in[b], -1);
  update(out[b] + 1, +1);
  ans[a] = newval;
  ans[b] = 0;
  activ[id] = true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m, q;
    cin>>n>>m>>q;
    for(int i = 1; i<n; i++){
      int x, y;
      cin>>x>>y;
      edg[i] = {x, y};
      gr[x].push_back(y);
      gr[y].push_back(x);

    }
    int cnt = 0;
    dfs_init(1, 0, cnt);
    for(int i = 1; i<n; i++){
      break_edge(i);
    }
    for(int i = 1; i<=n; i++)
      ans[i] = 1;
    for(int i = 1; i<=m; i++){
      int id;
      cin>>id;
      if(activ[id] == false)
        join_edge(id);
      else
        break_edge(id);
    }
    for(int i = 1; i<=q; i++){
      int c;
      cin>>c;
      cout<<ans[find_high(c)]<<"\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2772 KB Output is correct
6 Correct 3 ms 2956 KB Output is correct
7 Correct 15 ms 4256 KB Output is correct
8 Correct 14 ms 4224 KB Output is correct
9 Correct 14 ms 4236 KB Output is correct
10 Correct 229 ms 17668 KB Output is correct
11 Correct 314 ms 17720 KB Output is correct
12 Correct 361 ms 23808 KB Output is correct
13 Correct 72 ms 17588 KB Output is correct
14 Correct 225 ms 17024 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 20616 KB Output is correct
2 Correct 95 ms 20496 KB Output is correct
3 Correct 162 ms 23236 KB Output is correct
4 Correct 122 ms 23212 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2772 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2816 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 21 ms 4916 KB Output is correct
8 Correct 505 ms 24552 KB Output is correct
9 Correct 422 ms 24632 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 441 ms 24544 KB Output is correct
2 Correct 182 ms 24244 KB Output is correct
3 Correct 185 ms 24432 KB Output is correct
4 Correct 170 ms 24356 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2816 KB Output is correct
3 Correct 2 ms 2772 KB Output is correct
4 Correct 2 ms 2808 KB Output is correct
5 Correct 3 ms 2952 KB Output is correct
6 Correct 18 ms 4272 KB Output is correct
7 Correct 367 ms 18432 KB Output is correct
8 Correct 463 ms 24620 KB Output is correct
9 Correct 102 ms 18604 KB Output is correct
10 Correct 202 ms 18308 KB Output is correct
11 Correct 119 ms 21808 KB Output is correct
12 Correct 129 ms 21692 KB Output is correct
13 Correct 191 ms 24328 KB Output is correct