Submission #1064290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064290		earlyamazon	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	1103 ms	131072 KiB

ballmachine

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

const int mn = 1e5+7;
int n,q,korz;
vector<int> syny[mn];
int minn[mn];
bool zaj[mn];
int ojc[mn];

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

int dodaj(int v=korz){
    if (syny[v].empty()) return v;
    if (zaj[syny[v][0]] && zaj[syny[v][0]]) return v;
    if (zaj[syny[v][0]]) return dodaj(syny[v][1]);
    if (zaj[syny[v][1]]) return dodaj(syny[v][0]);
    if (minn[syny[v][1]] < minn[syny[v][0]]) return dodaj(syny[v][1]);
    return dodaj(syny[v][0]);
}

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 == 0) korz = i;
        else syny[a].push_back(korz);
    }
    dfsmin(korz);
    for (int i = 0; i < q; i++){
        int a,b,wyn;
        cin>>a>>b;
        if (a == 1){
            for (int j = 0; j < q; j++){
                wyn = dodaj();
                zaj[wyn] = 1;
            }
            cout<<wyn<<"\n";
        }
        else{
            int ile = 0;
            while (zaj[ojc[b]]){
                b = ojc[b];
                ile++;
            }
            zaj[b] = 0;
            cout<<ile<<"\n";
        }
    }
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:47:24: warning: 'wyn' may be used uninitialized in this function [-Wmaybe-uninitialized]
   47 |             cout<<wyn<<"\n";
      |                        ^~~~

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