oj.uz

Submission #412463

# Submission time Handle Problem Language Result Execution time Memory
412463 2021-05-27T00:17:10 Z Malheiros Synchronization (JOI13_synchronization) C++17
30 / 100
 548 ms 24400 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(i,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:135: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
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 Incorrect 3 ms 4556 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 133 ms 20940 KB Output isn't correct
2 Halted 0 ms 0 KB -

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 3 ms 4556 KB Output is correct
4 Correct 3 ms 4556 KB Output is correct
5 Correct 4 ms 4680 KB Output is correct
6 Correct 7 ms 4812 KB Output is correct
7 Correct 52 ms 6572 KB Output is correct
8 Correct 548 ms 23936 KB Output is correct
9 Correct 537 ms 24004 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 541 ms 23924 KB Output is correct
2 Correct 367 ms 24196 KB Output is correct
3 Correct 372 ms 24384 KB Output is correct
4 Correct 368 ms 24400 KB Output is correct

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4556 KB Output is correct
2 Incorrect 3 ms 4556 KB Output isn't correct
3 Halted 0 ms 0 KB -