oj.uz

Submission #412468

# Submission time Handle Problem Language Result Execution time Memory
412468 2021-05-27T00:21:00 Z Malheiros Synchronization (JOI13_synchronization) C++17
100 / 100
 593 ms 26912 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);
 
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;
    }
}

Compilation message

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.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 4556 KB Output is correct
5 Correct 3 ms 4684 KB Output is correct
6 Correct 5 ms 4796 KB Output is correct
7 Correct 20 ms 6092 KB Output is correct
8 Correct 21 ms 6080 KB Output is correct
9 Correct 23 ms 6104 KB Output is correct
10 Correct 302 ms 20056 KB Output is correct
11 Correct 252 ms 19856 KB Output is correct
12 Correct 316 ms 26056 KB Output is correct
13 Correct 116 ms 19816 KB Output is correct
14 Correct 156 ms 19268 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 20876 KB Output is correct
2 Correct 134 ms 22584 KB Output is correct
3 Correct 138 ms 25544 KB Output is correct
4 Correct 134 ms 25452 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4560 KB Output is correct
2 Correct 3 ms 4556 KB Output is correct
3 Correct 4 ms 4560 KB Output is correct
4 Correct 3 ms 4564 KB Output is correct
5 Correct 3 ms 4692 KB Output is correct
6 Correct 7 ms 4824 KB Output is correct
7 Correct 47 ms 6592 KB Output is correct
8 Correct 581 ms 24064 KB Output is correct
9 Correct 593 ms 24056 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 546 ms 24264 KB Output is correct
2 Correct 370 ms 24296 KB Output is correct
3 Correct 372 ms 24304 KB Output is correct
4 Correct 369 ms 24352 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 4 ms 4684 KB Output is correct
5 Correct 8 ms 4804 KB Output is correct
6 Correct 41 ms 6212 KB Output is correct
7 Correct 470 ms 20928 KB Output is correct
8 Correct 548 ms 26912 KB Output is correct
9 Correct 311 ms 20992 KB Output is correct
10 Correct 393 ms 20664 KB Output is correct
11 Correct 346 ms 24144 KB Output is correct
12 Correct 345 ms 24132 KB Output is correct
13 Correct 362 ms 26612 KB Output is correct