제출 #412468

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
412468		Malheiros	동기화 (JOI13_synchronization)	C++17	100 / 100	593 ms	26912 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);
 
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 t){
    auto u=edge[t].first;
    auto v=edge[t].second;
    if (ddepth[u]<ddepth[v])swap(u,v);
    //u eh o de baixo
    ans[getpar(v)]+=ans[u]-lazyness[u];
    f.update(beg[u],-1);
    f.update(en[u]+1,1);
}
 
 void rem(int t){
    auto u=edge[t].first;
    auto v=edge[t].second;
    if (ddepth[u]<ddepth[v])swap(u,v);
    //u eh o de baixo VER ISSO AQUI O
    ans[u]=ans[getpar(v)];
    lazyness[u]=ans[getpar(v)];
    f.update(beg[u],1);
    f.update(en[u]+1,-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++){
        f.update(beg[i],1);
        f.update(en[i]+1,-1);
    }
    //cout<<1<<endl;
    while(m--){
        int a;cin>>a;
        if (isset[a]){
            rem(a);
        }
        else{
            add(a);
        }
 
        isset[a]=!isset[a];
    }
 
    while(q--){
        int a;cin>>a;
        cout<<ans[getpar(a)]<<endl;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

In constructor 'fenwick::fenwick(int)',
    inlined from 'void __static_initialization_and_destruction_0(int, int)' at synchronization.cpp:69:15,
    inlined from '(static initializers for synchronization.cpp)' at synchronization.cpp:138: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