oj.uz

답안 #132823

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
132823 2019-07-19T16:55:19 Z muradeyn Ball Machine (BOI13_ballmachine) C++14
100 / 100
 189 ms 24428 KB 
/* Murad Eynizade */

#include <bits/stdc++.h>
#define intt long long
#define fyck ios_base::sync_with_stdio(0);cin.tie(0);
#define F first
#define S second
#define endl '\n'

using namespace std;

const int maxx = 100005 , lg = 17;

int n , q , x , ty , k , rt , nxt;

int par[maxx][lg] , dp[maxx] , used[maxx] , key[maxx];

bool cmp(int i,int j) {
    return dp[i] < dp[j];
}

vector<int>v[maxx];

priority_queue< pair<int,int> >pq;

void dfs(int s) {
    dp[s] = s;
    for (int to : v[s])dfs(to) , dp[s] = min(dp[s] , dp[to]);
    sort(v[s].begin(),v[s].end(),cmp);
}

void gen(int s) {
    for (int to : v[s])gen(to);
    key[s] = nxt--;
    pq.push({key[s] , s});
}

int main() {
    fyck
    cin>>n>>q;
    for (int i = 1;i<=n;i++) {
        cin>>x;
        if (x) {
            v[x].push_back(i);
            par[i][0] = x;
        }
        else rt = i;
    }
    for (int j = 1;j<lg;j++)
        for (int i = 1;i<=n;i++)
            par[i][j] = par[par[i][j - 1]][j - 1];
    dfs(rt);
    gen(rt);
    while (q--) {
        cin>>ty>>k;
        if (ty == 1) {
            while(k--) {
                x = pq.top().S;
                pq.pop();
                used[x] = 1;
            }
            cout<<x<<endl;
        }
        else {
            int res = 0;
            for (int i = lg - 1;i>=0;i--) {
                if (used[par[k][i]]) {
                    res += (1 << i);
                    k = par[k][i];
                }
            }
            cout<<res<<endl;
            used[k] = 0;
            pq.push({key[k] , k});
        }
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2808 KB Output is correct
2 Correct 97 ms 10864 KB Output is correct
3 Correct 69 ms 10608 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2808 KB Output is correct
6 Correct 5 ms 2808 KB Output is correct
7 Correct 5 ms 2808 KB Output is correct
8 Correct 5 ms 2808 KB Output is correct
9 Correct 9 ms 3192 KB Output is correct
10 Correct 22 ms 4728 KB Output is correct
11 Correct 115 ms 10892 KB Output is correct
12 Correct 69 ms 10616 KB Output is correct
13 Correct 110 ms 10808 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 7156 KB Output is correct
2 Correct 144 ms 18772 KB Output is correct
3 Correct 89 ms 13676 KB Output is correct
4 Correct 60 ms 8180 KB Output is correct
5 Correct 60 ms 8052 KB Output is correct
6 Correct 57 ms 8052 KB Output is correct
7 Correct 59 ms 7160 KB Output is correct
8 Correct 39 ms 7156 KB Output is correct
9 Correct 138 ms 19280 KB Output is correct
10 Correct 145 ms 18992 KB Output is correct
11 Correct 129 ms 18800 KB Output is correct
12 Correct 132 ms 16608 KB Output is correct
13 Correct 111 ms 21200 KB Output is correct
14 Correct 88 ms 13696 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 64 ms 11124 KB Output is correct
2 Correct 149 ms 17108 KB Output is correct
3 Correct 123 ms 19824 KB Output is correct
4 Correct 102 ms 15948 KB Output is correct
5 Correct 105 ms 15608 KB Output is correct
6 Correct 100 ms 15596 KB Output is correct
7 Correct 102 ms 14116 KB Output is correct
8 Correct 126 ms 19692 KB Output is correct
9 Correct 158 ms 19472 KB Output is correct
10 Correct 156 ms 19184 KB Output is correct
11 Correct 158 ms 19056 KB Output is correct
12 Correct 164 ms 17036 KB Output is correct
13 Correct 189 ms 24428 KB Output is correct
14 Correct 116 ms 14512 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 19572 KB Output is correct
2 Correct 151 ms 17080 KB Output is correct
3 Correct 125 ms 23572 KB Output is correct
4 Correct 170 ms 19708 KB Output is correct
5 Correct 160 ms 19188 KB Output is correct
6 Correct 142 ms 18928 KB Output is correct
7 Correct 150 ms 17128 KB Output is correct
8 Correct 127 ms 23712 KB Output is correct
9 Correct 85 ms 13764 KB Output is correct