oj.uz

Submission #643414

# Submission time Handle Problem Language Result Execution time Memory
643414 2022-09-22T02:40:50 Z GaLz Ball Machine (BOI13_ballmachine) C++14
100 / 100
 136 ms 24452 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll mod=1e9+7;
const ll maxn=1e5+5;
const ll INF=1e18;
#define ok ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define fi first
#define se second
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define endl '\n'
int n, q, t, x, mn[maxn], par[maxn], root, dis[maxn], hrs, cnt, ans, nmr[maxn], lca[maxn][17];
vi adj[maxn], arr;
bool use[maxn];
bool sub1=1;
priority_queue<pii, vector<pii>, greater<>> pq;
bool cmp(int a, int b) {
    return mn[a]<mn[b];
}
void dfs(int now, int fr) {
    mn[now]=now;
    lca[now][0]=fr;
    for(int i=1; i<17; i++) {
        lca[now][i]=lca[lca[now][i-1]][i-1];
    }
    for(auto it : adj[now]) {
        dis[it]=dis[now]+1;
        dfs(it, now);
        mn[now]=min(mn[now], mn[it]);
    }
}
void dfs2(int now) {
    if(!adj[now].empty()) {
        sort(adj[now].begin(), adj[now].end(), cmp);
        for(auto it : adj[now]) {
            dfs2(it);
        }
    }
    arr.pb(now);
}
int main() {
    // Bismillah AC
    ok
    cin >> n >> q;
    for(int i=1; i<=n; i++) {
        cin >> par[i];
        if(par[i]==0){
            root=i;
        } else adj[par[i]].pb(i);
    }
    dfs(root, 0);
    for(int i=1; i<=n; i++) {
        if(!(adj[i].size()==2 || adj[i].empty())) sub1=0;
        if(adj[i].empty() && hrs && dis[i]!=hrs) sub1=0;
        if(adj[i].empty() && !hrs) hrs=dis[i];
    }
    dfs2(root);
    for(auto it : arr) {
        cnt++;
        nmr[it]=cnt;
        pq.push({cnt, it});
    }
    while(q--) {
        cin >> t >> x;
        if(t==1) {
            while(x--) {
                ans=pq.top().se;
                use[pq.top().se]=1;
                pq.pop();
            }
            cout << ans << endl;
        } else {
            ans=0;
            while(use[par[x]]) {
                for(int i=16; i>=0; i--) {
                    if(use[lca[x][i]]) {
                        ans+=dis[x]-dis[lca[x][i]];
                        x=lca[x][i];
                        break;
                    }
                }
            }
            use[x]=0;
            pq.push({nmr[x], x});
            cout << ans << endl;
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 69 ms 10204 KB Output is correct
3 Correct 48 ms 10380 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 2 ms 2700 KB Output is correct
6 Correct 2 ms 2772 KB Output is correct
7 Correct 3 ms 2772 KB Output is correct
8 Correct 2 ms 2772 KB Output is correct
9 Correct 7 ms 3156 KB Output is correct
10 Correct 13 ms 4672 KB Output is correct
11 Correct 62 ms 10280 KB Output is correct
12 Correct 45 ms 10380 KB Output is correct
13 Correct 81 ms 10228 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 6728 KB Output is correct
2 Correct 101 ms 18312 KB Output is correct
3 Correct 63 ms 13764 KB Output is correct
4 Correct 35 ms 7624 KB Output is correct
5 Correct 36 ms 7472 KB Output is correct
6 Correct 39 ms 7632 KB Output is correct
7 Correct 40 ms 6616 KB Output is correct
8 Correct 27 ms 6776 KB Output is correct
9 Correct 86 ms 18740 KB Output is correct
10 Correct 96 ms 18244 KB Output is correct
11 Correct 94 ms 18284 KB Output is correct
12 Correct 97 ms 16088 KB Output is correct
13 Correct 83 ms 21156 KB Output is correct
14 Correct 61 ms 13764 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 10864 KB Output is correct
2 Correct 99 ms 16972 KB Output is correct
3 Correct 92 ms 19628 KB Output is correct
4 Correct 88 ms 15856 KB Output is correct
5 Correct 86 ms 15420 KB Output is correct
6 Correct 73 ms 15432 KB Output is correct
7 Correct 68 ms 13908 KB Output is correct
8 Correct 90 ms 19644 KB Output is correct
9 Correct 104 ms 19364 KB Output is correct
10 Correct 110 ms 18976 KB Output is correct
11 Correct 107 ms 18920 KB Output is correct
12 Correct 108 ms 16956 KB Output is correct
13 Correct 136 ms 24452 KB Output is correct
14 Correct 73 ms 13860 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 19492 KB Output is correct
2 Correct 122 ms 16956 KB Output is correct
3 Correct 89 ms 23504 KB Output is correct
4 Correct 119 ms 19488 KB Output is correct
5 Correct 115 ms 18492 KB Output is correct
6 Correct 105 ms 18400 KB Output is correct
7 Correct 114 ms 16944 KB Output is correct
8 Correct 93 ms 23500 KB Output is correct
9 Correct 57 ms 13816 KB Output is correct