oj.uz

Submission #411781

# Submission time Handle Problem Language Result Execution time Memory
411781 2021-05-25T23:29:55 Z Malheiros Synchronization (JOI13_synchronization) C++17
100 / 100
 510 ms 24444 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=1;
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];
    }

    
    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],-i);
}



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

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 4672 KB Output is correct
5 Correct 3 ms 4556 KB Output is correct
6 Correct 4 ms 4684 KB Output is correct
7 Correct 18 ms 5896 KB Output is correct
8 Correct 18 ms 5972 KB Output is correct
9 Correct 19 ms 5968 KB Output is correct
10 Correct 228 ms 17544 KB Output is correct
11 Correct 227 ms 17728 KB Output is correct
12 Correct 259 ms 23748 KB Output is correct
13 Correct 106 ms 17848 KB Output is correct
14 Correct 151 ms 17652 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 20760 KB Output is correct
2 Correct 128 ms 20572 KB Output is correct
3 Correct 129 ms 23796 KB Output is correct
4 Correct 134 ms 23792 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 3 ms 4556 KB Output is correct
4 Correct 3 ms 4684 KB Output is correct
5 Correct 4 ms 4556 KB Output is correct
6 Correct 7 ms 4864 KB Output is correct
7 Correct 41 ms 6580 KB Output is correct
8 Correct 510 ms 24084 KB Output is correct
9 Correct 489 ms 23932 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 24244 KB Output is correct
2 Correct 373 ms 24284 KB Output is correct
3 Correct 384 ms 24352 KB Output is correct
4 Correct 378 ms 24388 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 4680 KB Output is correct
5 Correct 6 ms 4684 KB Output is correct
6 Correct 38 ms 5968 KB Output is correct
7 Correct 441 ms 17852 KB Output is correct
8 Correct 489 ms 23944 KB Output is correct
9 Correct 296 ms 18476 KB Output is correct
10 Correct 362 ms 18296 KB Output is correct
11 Correct 337 ms 21480 KB Output is correct
12 Correct 338 ms 21464 KB Output is correct
13 Correct 365 ms 24444 KB Output is correct