Submission #411782

#	Time	Username	Problem	Language	Result	Execution time	Memory
411782		Malheiros	Synchronization (JOI13_synchronization)	C++17	100 / 100	539 ms	24460 KiB

synchronization

#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 (stderr)

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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40