oj.uz

Submission #545694

# Submission time Handle Problem Language Result Execution time Memory
545694 2022-04-05T08:03:24 Z shark25361 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 472 ms 61748 KB 
#include<bits/stdc++.h>
#include <iomanip>
using namespace std;

#define FIO ios_base::sync_with_stdio(false);cin.tie(0);
#define ll long long
#define for_t ll T;cin>>T;while(T--)
#define endl "\n"
#define mod 1000000007
#define inf 1000000000000000001
#define all(c) c.begin(),c.end()
#define pb push_back
#define lc(curr) (curr * 2)
#define rc(curr) ((curr * 2) + 1)

const int maxn = 100005;

vector<ll> adj[maxn];
ll parent[maxn];
vector<bool> hasball(maxn,false);
ll cnt,root,last;
ll minnode[maxn];//min node in the subtree of i
vector<ll> order;
map<ll,ll> mp;
set<pair<ll,ll>> nb;//these nodes do not have balls
ll tin[maxn];
ll tout[maxn];
ll timer = 0;
ll up[maxn][35];

//find the contiguous nodes in ancestors of i that have a ball
void remnode(ll i)
{
    ll cnt = 0;
    ll curr = i;
    for(int j = 30;j >= 0;j--)
    {
        if(hasball[up[curr][j]])
        {
            curr = up[curr][j];
            cnt += pow(2,j);
        }
    }
    hasball[curr] = false;
    nb.insert({mp[curr],curr});
    cout << cnt << endl;
}

bool comp(ll i,ll j)
{
    return minnode[i] < minnode[j];
}

void dfs(ll i)
{
    minnode[i] = i;
    for(auto it:adj[i])
    {
        dfs(it);
        minnode[i] = min(minnode[i],minnode[it]);
    }
}

void dfs2(ll i)
{
    for(auto it:adj[i])
    {
        dfs2(it);
        order.pb(it);
    }
    order.pb(i);
    mp[i] = order.size() - 1;
    nb.insert({mp[i],i});
}

void lcadfs(ll i,ll parent)
{
    tin[i] = timer++;
    up[i][0] = parent;
    for(int j = 1;j <= 30;j++)
    {
        up[i][j] = up[up[i][j - 1]][j - 1];
    }
    for(auto it:adj[i])
    {
        lcadfs(it,i);
    }
    tout[i] = timer++;
}

void sol()
{
    ll n,q;
    cin >> n >> q;
    for(int i = 1;i <= n;i++)
    {
        cin >> parent[i];
        if(parent[i] == 0)
        {
            root = i;
        }
        else
        {
            adj[parent[i]].pb(i);
        }
    }
    dfs(root);
    for(int i = 1;i <= n;i++)
    {
        sort(all(adj[i]),comp);
    }
    dfs2(root);
    memset(up,0,sizeof(up));
    lcadfs(root,0);
    for(int i = 0;i < q;i++)
    {
        ll x,y;
        cin >> x >> y;
        if(x == 1)
        {
            for(int j = 0;j < y;j++)
            {
                ll u = (*nb.begin()).second;
                hasball[u] = true;
                last = u;
                nb.erase(*nb.begin());
            }
            cout << last << endl;
        }
        else
        {
            remnode(y);
        }
    }
}

int main()
{
    FIO
    sol();
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 30036 KB Output is correct
2 Correct 271 ms 43816 KB Output is correct
3 Correct 137 ms 43760 KB Output is correct
4 Correct 14 ms 30036 KB Output is correct
5 Correct 15 ms 30036 KB Output is correct
6 Correct 15 ms 30216 KB Output is correct
7 Correct 16 ms 30240 KB Output is correct
8 Correct 19 ms 30292 KB Output is correct
9 Correct 25 ms 30924 KB Output is correct
10 Correct 51 ms 33352 KB Output is correct
11 Correct 259 ms 43672 KB Output is correct
12 Correct 156 ms 43692 KB Output is correct
13 Correct 221 ms 43876 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 36232 KB Output is correct
2 Correct 404 ms 55508 KB Output is correct
3 Correct 179 ms 49912 KB Output is correct
4 Correct 144 ms 38324 KB Output is correct
5 Correct 157 ms 38148 KB Output is correct
6 Correct 123 ms 38208 KB Output is correct
7 Correct 136 ms 36956 KB Output is correct
8 Correct 65 ms 36228 KB Output is correct
9 Correct 343 ms 55992 KB Output is correct
10 Correct 433 ms 55492 KB Output is correct
11 Correct 338 ms 55576 KB Output is correct
12 Correct 382 ms 52768 KB Output is correct
13 Correct 242 ms 57772 KB Output is correct
14 Correct 194 ms 49976 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 43092 KB Output is correct
2 Correct 472 ms 53524 KB Output is correct
3 Correct 298 ms 55104 KB Output is correct
4 Correct 285 ms 50728 KB Output is correct
5 Correct 276 ms 50576 KB Output is correct
6 Correct 296 ms 50336 KB Output is correct
7 Correct 267 ms 48448 KB Output is correct
8 Correct 298 ms 55084 KB Output is correct
9 Correct 422 ms 56164 KB Output is correct
10 Correct 429 ms 55756 KB Output is correct
11 Correct 464 ms 55780 KB Output is correct
12 Correct 437 ms 53460 KB Output is correct
13 Correct 461 ms 61748 KB Output is correct
14 Correct 366 ms 50428 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 56308 KB Output is correct
2 Correct 421 ms 53424 KB Output is correct
3 Correct 279 ms 61368 KB Output is correct
4 Correct 419 ms 56296 KB Output is correct
5 Correct 420 ms 55784 KB Output is correct
6 Correct 339 ms 55676 KB Output is correct
7 Correct 449 ms 53364 KB Output is correct
8 Correct 267 ms 61368 KB Output is correct
9 Correct 181 ms 49972 KB Output is correct