oj.uz

Submission #536451

# Submission time Handle Problem Language Result Execution time Memory
536451 2022-03-13T11:00:17 Z __Variatto Ball Machine (BOI13_ballmachine) C++17
100 / 100
 317 ms 36872 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int MAX=1e5+10, S=1<<19, L=19;
int n, q, a, b, mini[MAX], root, nr[MAX];
vector<int>g[MAX];
int pre[MAX], maxiPre[MAX], jump[MAX][L+1], czas=1;
void dfs1(int v, int oj){
    mini[v]=v;
    pre[v]=czas++;
    maxiPre[v]=pre[v];
    jump[v][0]=oj;
    for(int i=1; i<=L; i++)
        jump[v][i]=jump[jump[v][i-1]][i-1];
    for(auto s:g[v]){
        if(s!=oj){
            dfs1(s, v);
            mini[v]=min(mini[v], mini[s]);
            maxiPre[v]=max(maxiPre[v], maxiPre[s]);
        }
    }
}
int akt=1;
void dfs2(int v, int oj){
    int aktMini=MAX;
    set<pair<int,int>>x;
    for(auto s: g[v])
        if(s!=oj)
            x.insert({mini[s], s});
    for(set<pair<int,int>>::iterator it=x.begin(); it!=x.end(); it++)
        dfs2((*it).se, v);

    nr[v]=akt++;
}
int t[2*S+10];
void Insert(int a, int b,int x){
    a+=S-1, b+=S+1;
    while(a+1<b){
        if(a%2==0) t[a+1]+=x;
        if(b%2==1) t[b-1]+=x;
        a/=2, b/=2;
    }
}
int Query(int pos){
    int res=0;
    pos+=S;
    while(pos){
        res+=t[pos];
        pos/=2;
    }
    return res;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        cin>>a;
        if(!a)
            root=i;
        else
            g[i].pb(a), g[a].pb(i);
    }
    dfs1(root, root);
    dfs2(root, root);
    set<pair<int,int>>kol;
    for(int i=1; i<=n; i++)
        kol.insert({nr[i], i});
    while(q--){
        cin>>a>>b;
        if(a==1){
            while(b--){
                int v=(*kol.begin()).se;
                kol.erase(kol.begin());
                if(pre[v]+1<=maxiPre[v])
                    Insert(pre[v]+1, maxiPre[v], 1);
                if(!b)
                    cout<<v<<"\n";
            }
/*            for(int i=1; i<=n; i++)
                cout<<i<<" "<<pre[i]<<" "<<Query(1, 0, S-1, pre[i])<<"x\n";;
            cout<<"\n";
*/        }
        else{
            int wyn=Query(pre[b]);
            cout<<wyn<<"\n";
            int l=0, v=b;
            while(wyn){
                if(wyn%2)
                    v=jump[v][l];
                wyn/=2, l++;
            }
            Insert(pre[v]+1, maxiPre[v], -1);
            kol.insert({nr[v], v});
        }
    }
    
}

Compilation message

ballmachine.cpp: In function 'void dfs2(int, int)':
ballmachine.cpp:28:9: warning: unused variable 'aktMini' [-Wunused-variable]
   28 |     int aktMini=MAX;
      |         ^~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 155 ms 14608 KB Output is correct
3 Correct 98 ms 14356 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2768 KB Output is correct
6 Correct 4 ms 2900 KB Output is correct
7 Correct 3 ms 2900 KB Output is correct
8 Correct 3 ms 2900 KB Output is correct
9 Correct 8 ms 3500 KB Output is correct
10 Correct 24 ms 5716 KB Output is correct
11 Correct 161 ms 14576 KB Output is correct
12 Correct 83 ms 14344 KB Output is correct
13 Correct 136 ms 14228 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8952 KB Output is correct
2 Correct 202 ms 28492 KB Output is correct
3 Correct 108 ms 20232 KB Output is correct
4 Correct 81 ms 10636 KB Output is correct
5 Correct 75 ms 10532 KB Output is correct
6 Correct 66 ms 10316 KB Output is correct
7 Correct 73 ms 8892 KB Output is correct
8 Correct 53 ms 8876 KB Output is correct
9 Correct 210 ms 28412 KB Output is correct
10 Correct 224 ms 28400 KB Output is correct
11 Correct 197 ms 28132 KB Output is correct
12 Correct 239 ms 23904 KB Output is correct
13 Correct 132 ms 32076 KB Output is correct
14 Correct 114 ms 20172 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 15788 KB Output is correct
2 Correct 282 ms 25136 KB Output is correct
3 Correct 173 ms 29744 KB Output is correct
4 Correct 191 ms 23500 KB Output is correct
5 Correct 159 ms 23432 KB Output is correct
6 Correct 154 ms 23440 KB Output is correct
7 Correct 196 ms 20232 KB Output is correct
8 Correct 166 ms 29812 KB Output is correct
9 Correct 278 ms 28948 KB Output is correct
10 Correct 280 ms 28856 KB Output is correct
11 Correct 234 ms 28904 KB Output is correct
12 Correct 317 ms 24912 KB Output is correct
13 Correct 254 ms 36872 KB Output is correct
14 Correct 222 ms 20944 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 28724 KB Output is correct
2 Correct 305 ms 24780 KB Output is correct
3 Correct 178 ms 35936 KB Output is correct
4 Correct 233 ms 28836 KB Output is correct
5 Correct 279 ms 28500 KB Output is correct
6 Correct 184 ms 28088 KB Output is correct
7 Correct 237 ms 24676 KB Output is correct
8 Correct 207 ms 35920 KB Output is correct
9 Correct 113 ms 20260 KB Output is correct