oj.uz

Submission #448064

# Submission time Handle Problem Language Result Execution time Memory
448064 2021-07-28T17:04:34 Z Killer2501 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 462 ms 36412 KB 
#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define pii pair<ll, pll>
using namespace std;
using ll = int;
const int  N = 2e5+55;
const ll mod = 1e9+7;
const ll mod1 = 1e9+1;
const ll base = 311;
const ll base1 = 331;
ll m, n, t, k, a[N], tong, b[N], dp[N], c[N], lab[N], cnt, ans, P[N][20], h[N], d[N];
priority_queue< pll, vector<pll>, greater<pll> > pq;
string s[N];
vector<ll> adj[N];
vector<pll> e;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
bool cmp(const ll& x, const ll& y)
{
    return b[x] < b[y];
}
void dfs(ll u, ll p)
{
    for(int i = 1; i <= 18; i ++)P[u][i] = P[P[u][i-1]][i-1];
    b[u] = u;
    for(ll v : adj[u])
    {
        if(v == p)continue;
        P[v][0] = u;
        dfs(v, u);
        b[u] = min(b[u], b[v]);
    }
    if(p)
    {
        for(int i = 0; i < adj[u].size(); i ++)
        {
            if(adj[u][i] == p)
            {
                adj[u][i] = adj[u].back();
                adj[u].pop_back();
                break;
            }
        }
    }
    sort(adj[u].begin(), adj[u].end(), cmp);
}
void getid(ll u)
{
    for(ll v : adj[u])
    {
        //cout << u <<" "<<v<<'\n';
        h[v] = h[u] + 1;
        getid(v);
    }
    //cout << u <<" "<<h[u]<<'\n';
    d[u] = ++cnt;
}
ll par(ll u, ll dis)
{
    for(int i = 18; i >= 0; i --)if((dis >> i) & 1)u = P[u][i];
    return u;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        if(!a[i])k = i;
        else
        {
            adj[a[i]].pb(i);
            adj[i].pb(a[i]);
        }
    }
    //cout << k << '\n';
    dfs(k, 0);
    getid(k);
    for(int i = 1; i <= n; i ++)pq.push({d[i], i});
    while(m -- > 0)
    {
        ll x;
        cin >> t >> x;
        if(t == 1)
        {
            ans = 0;
            while(x -- > 0)
            {
                ans = pq.top().se;
                lab[ans] = 1;
                pq.pop();
            }
            cout << ans << '\n';
        }
        else
        {
            ll lf = 0, rt = h[x], mid;

            while(lf <= rt)
            {
                mid = (lf + rt) / 2;
                k = par(x, mid);
                if(lab[k])lf = mid + 1;
                else rt = mid - 1;
            }
            ans = par(x, rt);
            pq.push({d[ans], ans});
            lab[ans] = 0;
            //cout << ans << '\n';
            cout << h[x] - h[ans] << '\n';
        }
    }
}
/*
1
5 9
1 2 3 2
1 3 2 -2
2 2 3
1 3 2 -3
2 2 3
1 1 4 7
1 4 5 8
2 5 2
2 5 1
1 5 6
1 1 2 2
1 2 4 3
2 1 4
1 1 5 6
1 2 3 -2
2 3 5
*/

Compilation message

ballmachine.cpp: In function 'void dfs(ll, ll)':
ballmachine.cpp:46:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = 0; i < adj[u].size(); i ++)
      |                        ~~^~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11340 KB Output is correct
2 Correct 124 ms 21720 KB Output is correct
3 Correct 83 ms 21396 KB Output is correct
4 Correct 7 ms 11284 KB Output is correct
5 Correct 8 ms 11340 KB Output is correct
6 Correct 7 ms 11468 KB Output is correct
7 Correct 9 ms 11468 KB Output is correct
8 Correct 9 ms 11468 KB Output is correct
9 Correct 12 ms 11980 KB Output is correct
10 Correct 28 ms 13828 KB Output is correct
11 Correct 134 ms 21696 KB Output is correct
12 Correct 84 ms 21396 KB Output is correct
13 Correct 120 ms 21636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 16372 KB Output is correct
2 Correct 371 ms 31356 KB Output is correct
3 Correct 102 ms 26088 KB Output is correct
4 Correct 103 ms 17780 KB Output is correct
5 Correct 148 ms 17928 KB Output is correct
6 Correct 160 ms 17972 KB Output is correct
7 Correct 135 ms 16752 KB Output is correct
8 Correct 66 ms 16280 KB Output is correct
9 Correct 279 ms 31608 KB Output is correct
10 Correct 434 ms 31284 KB Output is correct
11 Correct 315 ms 31392 KB Output is correct
12 Correct 332 ms 28560 KB Output is correct
13 Correct 167 ms 32868 KB Output is correct
14 Correct 106 ms 26028 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 21440 KB Output is correct
2 Correct 444 ms 29180 KB Output is correct
3 Correct 289 ms 31124 KB Output is correct
4 Correct 215 ms 27364 KB Output is correct
5 Correct 258 ms 27448 KB Output is correct
6 Correct 268 ms 27320 KB Output is correct
7 Correct 243 ms 25312 KB Output is correct
8 Correct 268 ms 31072 KB Output is correct
9 Correct 266 ms 31564 KB Output is correct
10 Correct 391 ms 31468 KB Output is correct
11 Correct 414 ms 31544 KB Output is correct
12 Correct 457 ms 29288 KB Output is correct
13 Correct 462 ms 36412 KB Output is correct
14 Correct 149 ms 26856 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 445 ms 31628 KB Output is correct
2 Correct 409 ms 29116 KB Output is correct
3 Correct 179 ms 35660 KB Output is correct
4 Correct 363 ms 31648 KB Output is correct
5 Correct 412 ms 31488 KB Output is correct
6 Correct 302 ms 31484 KB Output is correct
7 Correct 352 ms 29152 KB Output is correct
8 Correct 180 ms 35692 KB Output is correct
9 Correct 121 ms 26028 KB Output is correct