oj.uz

Submission #859260

# Submission time Handle Problem Language Result Execution time Memory
859260 2023-10-10T02:37:13 Z 8pete8 Ball Machine (BOI13_ballmachine) C++14
65.5678 / 100
 1000 ms 42152 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include<bitset>
#include<list>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
//#define p push
#define pb push_back
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
#define int long long
const int mxn=1e5,mod=69,lg=30,root=80,inf=1e18;
vector<ppii>adj[mxn+10];
int up[mxn+10][lg+5],h[mxn+10],st,go[mxn+10];
bitset<mxn+10>on;
int ch=0;
int dfs(int cur,int p){
    int cm=inf;
    for(auto &i:adj[cur]){
        h[i.f]=h[cur]+1;
        ch=max(ch,h[i.f]);
        int k=dfs(i.f,cur);
        cm=min(cm,k);
        i.s.f=k;
    }
    return min(cm,cur);
}
int solve(int cur,int p){
    int cm=inf;
    for(auto &i:adj[cur])cm=min(cm,i.s.f);
    for(auto &i:adj[cur]){
        i.s.s=solve(i.f,cur);
        if(i.s.f==cm)go[cur]=i.s.s;
    }
    if(cm==inf)return go[cur]=cur;
    return go[cur];
}
int32_t main(){
    fastio
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a;cin>>a;
        if(a==0){
            st=i;
            continue;
        }
        adj[a].pb({i,{-1,-1}});
        up[i][0]=a;
    }
    priority_queue<pii>pq;
    dfs(st,-1);
    solve(st,-1);
    for(int j=1;j<=lg;j++)for(int i=1;i<=n;i++)up[i][j]=up[up[i][j-1]][j-1];
    while(m--){
        int t;cin>>t;
        if(t==1){
            int k;cin>>k; 
            int ans=0;
            for(int j=0;j<k;j++){
                while(!pq.empty()&&!on[pq.top().s])pq.pop();
                while(!pq.empty()&&on[up[pq.top().s][0]])pq.pop();
                if(pq.empty())pq.push({h[go[st]],go[st]}),on[go[st]]=true,ans=go[st];
                else{
                    int cur=pq.top().s;
                    cur=up[cur][0];
                    int cm=inf;
                    pq.pop();
                    for(auto i:adj[cur])if(!on[i.f])cm=min(cm,i.s.f);
                    for(auto i:adj[cur]){
                        if(i.s.f==cm){
                            pq.push({h[i.s.s],i.s.s}),on[i.s.s]=true,ans=i.s.s;
                            break;
                        }
                    }
                    if(cm==inf){
                        on[cur]=true;
                        ans=cur;
                        pq.push({h[cur],cur});
                    }
                }
            }
            cout<<ans<<'\n';
        }   
        else{
            int x,y,diff;cin>>x;
            y=x;
            for(int i=lg;i>=0;i--)if(on[up[x][i]])x=up[x][i];
            diff=h[y]-(h[x]+1);
            for(int i=0;i<=lg;i++)if(diff&(1<<i))y=up[y][i];
            on[x]=false;
            if(diff!=-1)pq.push({h[y],y});
            else{for(auto i:adj[x])pq.push({h[i.f],i.f});}
            cout<<diff+1<<'\n';
        }
    }
}

Subtask #1
9.61538461538 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 4956 KB Output isn't correct
2 Correct 90 ms 26412 KB Output is correct
3 Correct 46 ms 26156 KB Output is correct
4 Incorrect 1 ms 4696 KB Output isn't correct
5 Incorrect 1 ms 4956 KB Output isn't correct
6 Correct 1 ms 4956 KB Output is correct
7 Incorrect 2 ms 4952 KB Output isn't correct
8 Correct 2 ms 4956 KB Output is correct
9 Incorrect 6 ms 7304 KB Output isn't correct
10 Incorrect 16 ms 10076 KB Output isn't correct
11 Incorrect 101 ms 26416 KB Output isn't correct
12 Correct 45 ms 25940 KB Output is correct
13 Incorrect 87 ms 25936 KB Output isn't correct

Subtask #2
17.1428571429 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 12892 KB Output is correct
2 Correct 176 ms 38564 KB Output is correct
3 Correct 49 ms 34820 KB Output is correct
4 Incorrect 62 ms 15608 KB Output isn't correct
5 Incorrect 67 ms 15564 KB Output isn't correct
6 Incorrect 64 ms 15316 KB Output isn't correct
7 Incorrect 70 ms 15056 KB Output isn't correct
8 Correct 28 ms 12984 KB Output is correct
9 Correct 148 ms 38468 KB Output is correct
10 Correct 171 ms 38576 KB Output is correct
11 Incorrect 91 ms 37420 KB Output isn't correct
12 Incorrect 144 ms 37072 KB Output isn't correct
13 Correct 57 ms 36948 KB Output is correct
14 Correct 54 ms 34648 KB Output is correct

Subtask #3
37.1428571429 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 23504 KB Output is correct
2 Correct 155 ms 37572 KB Output is correct
3 Correct 84 ms 35284 KB Output is correct
4 Correct 78 ms 33224 KB Output is correct
5 Correct 86 ms 33224 KB Output is correct
6 Correct 89 ms 33440 KB Output is correct
7 Correct 80 ms 32456 KB Output is correct
8 Correct 95 ms 35340 KB Output is correct
9 Correct 132 ms 39784 KB Output is correct
10 Correct 147 ms 38828 KB Output is correct
11 Correct 150 ms 38600 KB Output is correct
12 Correct 141 ms 37504 KB Output is correct
13 Correct 145 ms 42152 KB Output is correct
14 Execution timed out 1075 ms 34320 KB Time limit exceeded

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 38608 KB Output isn't correct
2 Incorrect 169 ms 37320 KB Output isn't correct
3 Correct 60 ms 39860 KB Output is correct
4 Incorrect 141 ms 38724 KB Output isn't correct
5 Incorrect 135 ms 38168 KB Output isn't correct
6 Incorrect 93 ms 37696 KB Output isn't correct
7 Incorrect 132 ms 37420 KB Output isn't correct
8 Correct 60 ms 39764 KB Output is correct
9 Correct 50 ms 34564 KB Output is correct