oj.uz

Submission #309365

# Submission time Handle Problem Language Result Execution time Memory
309365 2020-10-03T10:27:33 Z nicolaalexandra Ball Machine (BOI13_ballmachine) C++14
100 / 100
 603 ms 25464 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2816 KB Output is correct
2 Correct 477 ms 13464 KB Output is correct
3 Correct 381 ms 13048 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 3 ms 2816 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 6 ms 2816 KB Output is correct
8 Correct 7 ms 2816 KB Output is correct
9 Correct 34 ms 3328 KB Output is correct
10 Correct 89 ms 5240 KB Output is correct
11 Correct 483 ms 13432 KB Output is correct
12 Correct 378 ms 13236 KB Output is correct
13 Correct 446 ms 13432 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 7160 KB Output is correct
2 Correct 531 ms 21496 KB Output is correct
3 Correct 402 ms 17708 KB Output is correct
4 Correct 341 ms 8776 KB Output is correct
5 Correct 331 ms 8696 KB Output is correct
6 Correct 327 ms 8696 KB Output is correct
7 Correct 322 ms 7928 KB Output is correct
8 Correct 265 ms 7160 KB Output is correct
9 Correct 512 ms 21880 KB Output is correct
10 Correct 526 ms 21496 KB Output is correct
11 Correct 494 ms 21368 KB Output is correct
12 Correct 532 ms 20088 KB Output is correct
13 Correct 420 ms 22264 KB Output is correct
14 Correct 398 ms 17776 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 12152 KB Output is correct
2 Correct 570 ms 20472 KB Output is correct
3 Correct 358 ms 20600 KB Output is correct
4 Correct 361 ms 18040 KB Output is correct
5 Correct 364 ms 17660 KB Output is correct
6 Correct 362 ms 17656 KB Output is correct
7 Correct 364 ms 16660 KB Output is correct
8 Correct 360 ms 20728 KB Output is correct
9 Correct 578 ms 22136 KB Output is correct
10 Correct 577 ms 21752 KB Output is correct
11 Correct 567 ms 21752 KB Output is correct
12 Correct 603 ms 20472 KB Output is correct
13 Correct 592 ms 25464 KB Output is correct
14 Correct 536 ms 18548 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 22264 KB Output is correct
2 Correct 562 ms 20600 KB Output is correct
3 Correct 450 ms 24568 KB Output is correct
4 Correct 567 ms 22264 KB Output is correct
5 Correct 558 ms 21792 KB Output is correct
6 Correct 510 ms 21656 KB Output is correct
7 Correct 562 ms 20348 KB Output is correct
8 Correct 437 ms 24620 KB Output is correct
9 Correct 400 ms 17780 KB Output is correct