oj.uz

Submission #411780

# Submission time Handle Problem Language Result Execution time Memory
411780 2021-05-25T23:27:36 Z Malheiros Synchronization (JOI13_synchronization) C++17
100 / 100
 503 ms 26972 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 && dp[u][i - 1]; 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; i--) {
        if (dp[lca][i] && 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 4616 KB Output is correct
5 Correct 3 ms 4660 KB Output is correct
6 Correct 4 ms 4812 KB Output is correct
7 Correct 16 ms 6168 KB Output is correct
8 Correct 15 ms 6092 KB Output is correct
9 Correct 19 ms 6160 KB Output is correct
10 Correct 212 ms 19952 KB Output is correct
11 Correct 211 ms 19948 KB Output is correct
12 Correct 270 ms 26156 KB Output is correct
13 Correct 122 ms 19852 KB Output is correct
14 Correct 140 ms 19376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 20868 KB Output is correct
2 Correct 102 ms 22616 KB Output is correct
3 Correct 127 ms 25512 KB Output is correct
4 Correct 127 ms 25440 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 4 ms 4656 KB Output is correct
4 Correct 4 ms 4556 KB Output is correct
5 Correct 5 ms 4684 KB Output is correct
6 Correct 7 ms 4812 KB Output is correct
7 Correct 46 ms 6824 KB Output is correct
8 Correct 492 ms 26960 KB Output is correct
9 Correct 503 ms 26972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 495 ms 23976 KB Output is correct
2 Correct 389 ms 26444 KB Output is correct
3 Correct 358 ms 26604 KB Output is correct
4 Correct 391 ms 26628 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 4684 KB Output is correct
5 Correct 6 ms 4812 KB Output is correct
6 Correct 35 ms 6232 KB Output is correct
7 Correct 414 ms 20712 KB Output is correct
8 Correct 499 ms 26880 KB Output is correct
9 Correct 272 ms 20908 KB Output is correct
10 Correct 321 ms 20676 KB Output is correct
11 Correct 292 ms 24004 KB Output is correct
12 Correct 294 ms 23988 KB Output is correct
13 Correct 390 ms 26692 KB Output is correct