Submission #309365

#	Time	Username	Problem	Language	Result	Execution time	Memory
309365		nicolaalexandra	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	603 ms	25464 KiB

ballmachine

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

vector <int> L[DIM];
set <int> s;
int v[DIM],dp[DIM],poz[DIM],stramos[22][DIM],f[DIM];
int n,q,i,j,x,k,rad,tip;

void dfs (int nod){
    dp[nod] = nod;
    for (auto vecin : L[nod]){
        dfs (vecin);
        dp[nod] = min (dp[nod],dp[vecin]);
    }
}

void dfs2 (int nod){
    for (auto vecin : L[nod])
        dfs2 (vecin);
    v[++k] = nod;
}


inline int cmp (int a, int b){
    return dp[a] < dp[b];
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>q;
    for (i=1;i<=n;i++){
        cin>>x;
        if (!x)
            rad = i;
        else {
            L[x].push_back(i);
            stramos[0][i] = x;
        }
    }

    dfs (rad);

    for (i=1;i<=n;i++)
        sort (L[i].begin(),L[i].end(),cmp);

    dfs2 (rad);

    for (i=1;(1<<i)<=n;i++)
        for (j=1;j<=n;j++)
            stramos[i][j] = stramos[i-1][stramos[i-1][j]];

    /// tin un set cu nodurile libere
    for (i=1;i<=n;i++){
        s.insert(i);
        poz[v[i]] = i;
    }

    for (;q--;){
        cin>>tip>>x;
        if (tip == 1){ /// adaug x bile
            int sol;
            for (i=1;i<=x;i++){
                sol = v[*s.begin()];
                f[sol] = 1;
                s.erase(s.begin());
            }
            cout<<sol<<"\n";

        } else {
            int sol = 0;
            for (i=20;i>=0;i--){
                if (stramos[i][x] && f[stramos[i][x]]){
                    x = stramos[i][x];
                    sol += (1<<i);
                }
            }

            f[x] = 0;
            s.insert(poz[x]);

            cout<<sol<<"\n";

        }
    }

    return 0;
}

Compilation message (stderr)

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

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