oj.uz

Submission #411782

# Submission time Handle Problem Language Result Execution time Memory
411782 2021-05-25T23:31:43 Z Malheiros Synchronization (JOI13_synchronization) C++17
100 / 100
 539 ms 24460 KB 
#include <bits/stdc++.h>
    
using namespace std;

const int maxn=1e5+10;
const int maxlog=20;

#define ll long long

struct fenwick{

    ll* arr;
    int size;
    fenwick(int v){
        int n=v;
        arr= new ll[n+1];
        size=n;
        for (int i=0;i<=n+1;i++) arr[i]=0;
    }
    fenwick(vector<int>& v){
        int n=v.size();
        arr = new ll[n+1];
        size=n;
        for (int i=0;i<n;i++){
            arr[i+1]=v[i];
        }
        build();
    }
    void build () {
        for (int i=1;i<=size;i++){
            int j= i + (i & (-i));
            if (j<=size)arr[j]+=arr[i];
        }
    }
    void update(int i,int delta){
        for (;i<=size;i += i&(-i))arr[i]+=delta;
    }
    ll query(int i){
        ll soma=0;
        for (;i;i-= i &(-i))soma+=arr[i];
        return soma;
    }
    ll query(int l,int r){
        if (l==1)return query(r);
        return query(r)-query(l-1);
    }
};

int beg[maxn];
int en[maxn];
int ddepth[maxn];
int tempo=0;
int pai[maxn];
int dp[maxn][maxlog];
vector<int>grafo[maxn];
void dfs(int u,int p,int cc=0){
    ddepth[u]=cc;
    dp[u][0]=p;
    for (int i = 1; i < 20 ; i++) {
        dp[u][i] = dp[dp[u][i - 1]][i - 1];
    }

    tempo++;
    beg[u]=tempo;
    for (auto k:grafo[u]) if (k!=p) dfs(k,u,cc+1);
    en[u]=tempo;
}



fenwick f(maxn);
void updt(int u,int i){
    //cout<<beg[u]<<" : "<<en[u]<<endl;
    f.update(beg[u],i);
    f.update(en[u]+1,-i);
}



int getpar(int u){
    int teste = u;
    for (int i = 19; i>=0; i--) {
        if (f.query(beg[dp[teste][i]]) == f.query(beg[u])) teste = dp[teste][i];
    }
    return teste;
}

pair<int,int> edge[maxn];
vector<int> isset(maxn,false);
vector<int> ans(maxn,1);
vector<int> lazyness(maxn,0);
void add(int ind){
    auto u=edge[ind].first;
    auto v=edge[ind].second;
    if (dp[u][0]==v) swap(u,v);
    ans[v]= lazyness[v] = ans[getpar(u)];
    updt(v,1);
}
void rem(int ind){
    auto u=edge[ind].first;
    auto v=edge[ind].second;
    if (dp[u][0]==v) swap(u,v);
    ans[getpar(u)]+=ans[v]-lazyness[v];
    updt(v,-1);
}
int main(){
    cin.tie(NULL);cin.sync_with_stdio(false);
    int n,m,q;cin>>n>>m>>q;
    for (int i=1;i<n;i++){
        int a,b;cin>>a>>b;
        grafo[a].push_back(b);
        grafo[b].push_back(a);
        edge[i]={a,b};
    }
    dfs(1,0);

    for (int i=1;i<=n;i++) updt(i,1);
    //cout<<1<<endl;
    while(m--){
        int a;cin>>a;
        if (isset[a]){
            add(a);
        }
        else{
            rem(a);
        }
        isset[a]=!isset[a];
    }

    while(q--){
        int a;cin>>a;
        cout<<ans[getpar(a)]<<endl;
    }
}

Compilation message

In constructor 'fenwick::fenwick(int)',
    inlined from 'void __static_initialization_and_destruction_0(int, int)' at synchronization.cpp:71:15,
    inlined from '(static initializers for synchronization.cpp)' at synchronization.cpp:134:1:
synchronization.cpp:18:40: warning: 'void* __builtin_memset(void*, int, long unsigned int)' forming offset [800088, 800095] is out of the bounds [0, 800088] [-Warray-bounds]
   18 |         for (int i=0;i<=n+1;i++) arr[i]=0;
      |                                  ~~~~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 3 ms 4556 KB Output is correct
3 Correct 3 ms 4556 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 3 ms 4680 KB Output is correct
6 Correct 4 ms 4684 KB Output is correct
7 Correct 18 ms 5964 KB Output is correct
8 Correct 19 ms 5972 KB Output is correct
9 Correct 22 ms 5976 KB Output is correct
10 Correct 243 ms 17604 KB Output is correct
11 Correct 235 ms 17732 KB Output is correct
12 Correct 293 ms 23800 KB Output is correct
13 Correct 112 ms 17916 KB Output is correct
14 Correct 156 ms 17648 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 20876 KB Output is correct
2 Correct 122 ms 20668 KB Output is correct
3 Correct 131 ms 23720 KB Output is correct
4 Correct 132 ms 23732 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 3 ms 4556 KB Output is correct
3 Correct 5 ms 4556 KB Output is correct
4 Correct 4 ms 4556 KB Output is correct
5 Correct 4 ms 4684 KB Output is correct
6 Correct 7 ms 4864 KB Output is correct
7 Correct 42 ms 6580 KB Output is correct
8 Correct 512 ms 23988 KB Output is correct
9 Correct 497 ms 23980 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 23924 KB Output is correct
2 Correct 375 ms 24320 KB Output is correct
3 Correct 371 ms 24460 KB Output is correct
4 Correct 368 ms 24388 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 3 ms 4556 KB Output is correct
3 Correct 3 ms 4556 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 7 ms 4684 KB Output is correct
6 Correct 41 ms 5968 KB Output is correct
7 Correct 486 ms 17832 KB Output is correct
8 Correct 539 ms 23924 KB Output is correct
9 Correct 323 ms 18452 KB Output is correct
10 Correct 354 ms 18340 KB Output is correct
11 Correct 338 ms 21428 KB Output is correct
12 Correct 346 ms 21420 KB Output is correct
13 Correct 387 ms 24276 KB Output is correct