제출 #1064181

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1064181		earlyamazon	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	116 ms	36436 KiB

ballmachine

/**
 * @file msz.cpp
 * @author Marek Kycia
 * @brief Wzo - O(n * logn)
 */

#include <bits/stdc++.h>
using namespace std;

const int mn = 1e5+7;
const int K = 16;
int n,q;
int korz, licz;
vector<int> syny[mn];
int minn[mn];
int nr[mn];
int revnr[mn];
int jp[mn][K+1]; // z kolejnoscia
bool czyw[mn]; // z kolejnoscia
int gle[mn]; //z kolejnoscia
set<int> wolne;

void dfsmin(int v){
    minn[v] = v;
    for (auto i : syny[v]){
        dfsmin(i);
        minn[v] = min(minn[v], minn[i]);
    }
}

void dfsnr(int v){
    vector<pair<int,int>> pom;
    for (auto i : syny[v]){
        pom.push_back({minn[i], i});
    }
    sort(pom.begin(), pom.end());
    for (auto i : pom){
        dfsnr(i.second);
    }
    nr[v] = ++licz;
    revnr[licz] = v;
}

void dfsgle(int v){
    for (auto i : syny[v]){
        jp[nr[i]][0] = nr[v];
        gle[nr[i]] = gle[nr[v]]+1;
        dfsgle(i);
    }
}

int najwyzszy(int v){
    // cout<<"naj: "<<v<<" ";
    for (int i = K; i >= 0; i--){
        if (czyw[jp[v][i]]) v = jp[v][i];
        // cout<<v<<" ";
    }
    // cout<<"\n";
    return v;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for (int i = 1; i <= n; i++){
        int a;
        cin>>a;
        if (!a) korz = i;
        else syny[a].push_back(i);
        wolne.insert(i);
    }
    dfsmin(korz);
    dfsnr(korz);
    dfsgle(korz);
    for (int i = 1; i <= K; i++){
        for (int j = 1; j <= n; j++){
            jp[j][i] = jp[jp[j][i-1]][i-1];
            // cout<<jp[j][i]<<" ";
        }
        // cout<<"\n";
    }
    // for (int i = 1; i <= n; i++){
    //     cout<<nr[i]<<" ";
    // }
    // cout<<"\n";
    for (int i = 0; i < q; i++){
        int a,b,wyn=0;
        cin>>a>>b;
        if (a == 1){
            for (int j = 0; j < b; j++){
                wyn = *wolne.begin();
                czyw[wyn] = 1;
                wolne.erase(wolne.begin());
                // cout<<wyn<<" ";
            }
            // cout<<"\n";
            cout<<revnr[wyn]<<"\n";
        }
        else{
            int x = najwyzszy(nr[b]);
            wolne.insert(x);
            // cout<<b<<" "<<nr[b]<<" "<<x<<"\n";
            czyw[x] = 0;
            cout<<gle[nr[b]]-gle[x]<<"\n";
        }
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5