oj.uz

답안 #88557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
88557 2018-12-06T12:53:49 Z fasterthanyou Ball Machine (BOI13_ballmachine) C++14
100 / 100
 351 ms 50424 KB 
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

int n, q, root, timer=0;
bool ball[100015];
int p[25][100015], r[100015], h[100015];
pair<int, int> info[100015];
vector<int> g[100015];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > heap;

void Input()
{
    memset(p, -1, sizeof p);
    cin >> n >> q;
    for (int i=1, x; i<=n; ++i)
    {
        cin >> x;
        g[x].push_back(i);
        p[0][i]=x;
    }
}

void dfs(int u)
{
    r[u]=u;
    for (int i=0; i<(int)g[u].size(); ++i)
    {
        h[g[u][i]]=h[u]+1;
        dfs(g[u][i]);
        r[u]=min(r[u], r[g[u][i]]);
    }
}

void enqueue(int u)
{
    vector<pair<int, int> > a;
    for (int i=0; i<(int)g[u].size(); ++i)
        a.push_back({r[g[u][i]], g[u][i]});
    sort(a.begin(), a.end());
    for (int i=0; i<(int)a.size(); ++i)
        enqueue(a[i].second);
    heap.push({++timer, u});
    info[u]={timer, u};
}

void Solve()
{
    h[0]=0;
    dfs(0);
    enqueue(0);
    for (int i=1; (1<<i)<=n; ++i)
        for (int u=1; u<=n; ++u)
            if (p[i-1][u]!=-1)
                p[i][u]=p[i-1][p[i-1][u]];
    for (; q; --q)
    {
        int t, x;
        cin >> t >> x;
        if (t==1)
        {
            for (int i=0; i<x; ++i)
            {
                if (i==x-1) cout << heap.top().second << '\n';
                 ball[heap.top().second]=true;
                heap.pop();
            }
        } else
        {
            int u=x;
            for (int i=log2(h[u]); i>=0; --i)
                if (p[i][x]!=-1 && ball[p[i][x]]) x=p[i][x];
            ball[x]=false;
            heap.push(info[x]);
            cout << h[u]-h[x] << '\n';
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    //freopen("ball.inp", "r", stdin);
    //freopen("ball.out", "w", stdout);
    Input();
    Solve();
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12536 KB Output is correct
2 Correct 131 ms 15728 KB Output is correct
3 Correct 71 ms 15896 KB Output is correct
4 Correct 11 ms 15896 KB Output is correct
5 Correct 13 ms 15896 KB Output is correct
6 Correct 12 ms 15896 KB Output is correct
7 Correct 12 ms 15896 KB Output is correct
8 Correct 14 ms 15896 KB Output is correct
9 Correct 18 ms 15896 KB Output is correct
10 Correct 29 ms 15896 KB Output is correct
11 Correct 145 ms 16764 KB Output is correct
12 Correct 76 ms 17860 KB Output is correct
13 Correct 118 ms 18960 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 53 ms 20052 KB Output is correct
2 Correct 335 ms 29048 KB Output is correct
3 Correct 89 ms 29048 KB Output is correct
4 Correct 97 ms 29048 KB Output is correct
5 Correct 103 ms 29048 KB Output is correct
6 Correct 106 ms 29048 KB Output is correct
7 Correct 97 ms 29048 KB Output is correct
8 Correct 52 ms 29048 KB Output is correct
9 Correct 285 ms 33320 KB Output is correct
10 Correct 312 ms 35332 KB Output is correct
11 Correct 223 ms 36768 KB Output is correct
12 Correct 296 ms 36768 KB Output is correct
13 Correct 137 ms 43784 KB Output is correct
14 Correct 91 ms 43784 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 43784 KB Output is correct
2 Correct 284 ms 43784 KB Output is correct
3 Correct 203 ms 43784 KB Output is correct
4 Correct 166 ms 43784 KB Output is correct
5 Correct 187 ms 43784 KB Output is correct
6 Correct 187 ms 43784 KB Output is correct
7 Correct 180 ms 43784 KB Output is correct
8 Correct 218 ms 43784 KB Output is correct
9 Correct 238 ms 43784 KB Output is correct
10 Correct 322 ms 43784 KB Output is correct
11 Correct 323 ms 43784 KB Output is correct
12 Correct 288 ms 43784 KB Output is correct
13 Correct 320 ms 47764 KB Output is correct
14 Correct 126 ms 47764 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 297 ms 47764 KB Output is correct
2 Correct 351 ms 47764 KB Output is correct
3 Correct 153 ms 48864 KB Output is correct
4 Correct 294 ms 48864 KB Output is correct
5 Correct 310 ms 48864 KB Output is correct
6 Correct 224 ms 48864 KB Output is correct
7 Correct 287 ms 48864 KB Output is correct
8 Correct 152 ms 50424 KB Output is correct
9 Correct 87 ms 50424 KB Output is correct