답안 #411783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
411783 2021-05-25T23:41:13 Z Malheiros 동기화 (JOI13_synchronization) C++17
100 / 100
558 ms 24412 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 (ddepth[u]>ddepth[v]) swap(u,v);
    ans[v]= ans[getpar(u)];
    lazyness[v]=ans[getpar(u)];
    updt(v,1);
}
void rem(int ind){
    auto u=edge[ind].first;
    auto v=edge[ind].second;
    if (ddepth[u]>ddepth[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);
    //for (int i=1;i<=n;i++) cout<<f.query(beg[i])<<" ";
    //cout<<endl;
   // updt(2,1);
    //for (int i=1;i<=n;i++) cout<<f.query(beg[i])<<" ";
    //cout<<endl;
    //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:140: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;
      |                                  ~~~~~~^~
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 3 ms 4556 KB Output is correct
3 Correct 3 ms 4640 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 3 ms 4684 KB Output is correct
6 Correct 6 ms 4804 KB Output is correct
7 Correct 21 ms 5964 KB Output is correct
8 Correct 21 ms 5972 KB Output is correct
9 Correct 21 ms 5964 KB Output is correct
10 Correct 247 ms 17652 KB Output is correct
11 Correct 262 ms 17656 KB Output is correct
12 Correct 322 ms 23788 KB Output is correct
13 Correct 116 ms 17944 KB Output is correct
14 Correct 149 ms 17536 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 20880 KB Output is correct
2 Correct 128 ms 20680 KB Output is correct
3 Correct 130 ms 23752 KB Output is correct
4 Correct 128 ms 23748 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Correct 4 ms 4556 KB Output is correct
3 Correct 4 ms 4556 KB Output is correct
4 Correct 5 ms 4684 KB Output is correct
5 Correct 3 ms 4556 KB Output is correct
6 Correct 7 ms 4812 KB Output is correct
7 Correct 43 ms 6548 KB Output is correct
8 Correct 540 ms 23920 KB Output is correct
9 Correct 552 ms 24060 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 23928 KB Output is correct
2 Correct 390 ms 24344 KB Output is correct
3 Correct 377 ms 24392 KB Output is correct
4 Correct 364 ms 24360 KB Output is correct
# 결과 실행 시간 메모리 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 6 ms 4684 KB Output is correct
6 Correct 41 ms 6092 KB Output is correct
7 Correct 495 ms 17952 KB Output is correct
8 Correct 558 ms 24004 KB Output is correct
9 Correct 343 ms 18364 KB Output is correct
10 Correct 359 ms 18268 KB Output is correct
11 Correct 348 ms 21456 KB Output is correct
12 Correct 361 ms 21412 KB Output is correct
13 Correct 375 ms 24412 KB Output is correct