oj.uz

Submission #621299

# Submission time Handle Problem Language Result Execution time Memory
621299 2022-08-03T16:59:19 Z 353cerega Ball Machine (BOI13_ballmachine) C++17
100 / 100
 424 ms 46360 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>


using namespace std;


using ll = long long;
using ld = long double;

#define X first
#define Y second

//const ll mod = 1000000007;
const ll mod = 998244353;

vector<vector<ll>> g, up;
vector<ll> mn;
ll K = 20;

void dfs0(ll u)
{
    mn[u] = u;
    for (ll j=1;j<K;j++)
    {
        up[u][j] = up[up[u][j-1]][j-1];
    }
    for (ll v: g[u])
    {
        dfs0(v);
        mn[u] = min(mn[u],mn[v]);
    }
}

vector<ll> Q;

void dfs(ll u)
{
    vector<pair<ll,ll>> ord;
    for (ll v: g[u])
    {
        ord.push_back({mn[v],v});
    }
    sort(ord.begin(),ord.end());
    for (auto x: ord) dfs(x.Y);
    Q.push_back(u);
}

void solve()
{
    ll n, q;
    cin >> n >> q;
    g.resize(n+1);
    mn.resize(n+1);
    up.resize(n+1,vector<ll>(K));
    for (ll i=1;i<=n;i++)
    {
        ll x;
        cin >> x;
        up[i][0] = x;
        g[x].push_back(i);
    }
    dfs0(0);
    dfs(0);
    vector<ll> Q2(n+1);
    for (ll i=0;i<=n;i++) Q2[Q[i]] = i;
    set<ll> kek;
    for (ll i=0;i<=n;i++) kek.insert(i);
    vector<ll> was(n+1);
    while (q--)
    {
        ll t;
        ll x;
        cin >> t >> x;
        if (t==1)
        {
            ll L = 0;
            while (x--)
            {
                L = *kek.begin();
                kek.erase(L);
                was[Q[L]] = 1;
            }
            cout << Q[L] << "\n";
            continue;
        }
        ll A = 0;
        for (ll j=K-1;j>=0;j--)
        {
            if (was[up[x][j]]==1)
            {
                A += (1LL<<j);
                x = up[x][j];
            }
        }
        cout << A << "\n";
        was[x] = 0;
        kek.insert(Q2[x]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    ll T;
    T = 1;
    //cin >> T;
    while (T--) solve();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 260 ms 22112 KB Output is correct
3 Correct 206 ms 22100 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 3 ms 596 KB Output is correct
8 Correct 3 ms 584 KB Output is correct
9 Correct 15 ms 1608 KB Output is correct
10 Correct 48 ms 5732 KB Output is correct
11 Correct 277 ms 22116 KB Output is correct
12 Correct 202 ms 22336 KB Output is correct
13 Correct 243 ms 22316 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 9240 KB Output is correct
2 Correct 347 ms 39284 KB Output is correct
3 Correct 237 ms 32760 KB Output is correct
4 Correct 176 ms 12528 KB Output is correct
5 Correct 175 ms 12344 KB Output is correct
6 Correct 167 ms 12440 KB Output is correct
7 Correct 177 ms 10824 KB Output is correct
8 Correct 130 ms 9220 KB Output is correct
9 Correct 334 ms 39500 KB Output is correct
10 Correct 355 ms 39348 KB Output is correct
11 Correct 306 ms 39152 KB Output is correct
12 Correct 326 ms 35520 KB Output is correct
13 Correct 269 ms 40768 KB Output is correct
14 Correct 239 ms 32708 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 19908 KB Output is correct
2 Correct 375 ms 36556 KB Output is correct
3 Correct 273 ms 37028 KB Output is correct
4 Correct 239 ms 32060 KB Output is correct
5 Correct 238 ms 31616 KB Output is correct
6 Correct 252 ms 31664 KB Output is correct
7 Correct 236 ms 28996 KB Output is correct
8 Correct 243 ms 36960 KB Output is correct
9 Correct 371 ms 39764 KB Output is correct
10 Correct 424 ms 39308 KB Output is correct
11 Correct 379 ms 39344 KB Output is correct
12 Correct 393 ms 36560 KB Output is correct
13 Correct 407 ms 46360 KB Output is correct
14 Correct 321 ms 33316 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 39912 KB Output is correct
2 Correct 385 ms 36528 KB Output is correct
3 Correct 298 ms 45888 KB Output is correct
4 Correct 392 ms 39788 KB Output is correct
5 Correct 416 ms 39244 KB Output is correct
6 Correct 344 ms 39492 KB Output is correct
7 Correct 365 ms 36664 KB Output is correct
8 Correct 351 ms 45948 KB Output is correct
9 Correct 222 ms 32840 KB Output is correct