Submission #666900

#	Time	Username	Problem	Language	Result	Execution time	Memory
666900		Hacv16	Ball Machine (BOI13_ballmachine)	C++17	35.51 / 100	1091 ms	28228 KiB

ballmachine

    #include<bits/stdc++.h>
    using namespace std;
     
    typedef long long ll;
     
    const int MAX = 1e5 + 10;
    const int LOG = 20;
    const int INF = 0x3f3f3f3f;
     
    int n, q, filled[MAX], root, t, order[MAX], dp[MAX][LOG], d[MAX], mn[MAX];
    vector<int> adj[MAX];
    set<pair<int, int>> s;
     
    void dfs(int u, int p, int dist){
        d[u] = dist;
        mn[u] = u;
     
        for(auto v : adj[u]){
            if(v == p) continue;
            dfs(v, u, dist + 1);
            mn[u] = min(mn[u], mn[v]);
        }
    }
     
    ll query(ll u){
        int d1 = d[u];
     
        for(int i = LOG - 1; i >= 0; i--){
            int j = dp[u][i];
            if(j == -1) continue;
            if(filled[j]) u = j;
        }
     
        return d1 - d[u];
    }
     
    void dfs2(int u, int p){
        for(auto v : adj[u]){
            if(v == p) continue;
            dfs2(v, u);
        }
     
        order[u] = ++t;
        s.insert({order[u], u});
    }
     
    bool cmp(int u, int v){
        return mn[u] < mn[v];
    }
     
    int main(){
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
     
        cin >> n >> q;
     
        memset(dp, -1, sizeof(dp));
     
        for(int i = 1; i <= n; i++){
            int x; cin >> x;
     
            if(x != 0){
                adj[x].push_back(i);
                adj[i].push_back(x);
                dp[i][0] = x;
     
            }else{ root = i; }
        }
     
        dfs(root, -1, 0);
     
        for(int i = 1; i <= n; i++)
            sort(adj[i].begin(), adj[i].end(), cmp);
     
        dfs2(root, -1);
     
        for(int j = 1; j < LOG; j++){
            for(int i = 1; i <= n; i++){
                if(dp[i][j - 1] == -1) continue;
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        }
     
        while(q--){
            int op, k; cin >> op >> k;
     
            if(op == 1){
                int last = -1;
     
                assert(s.size());
     
                while(k--){
                    pair<int, int> b = *(s.begin());
                    int cur = b.second;
                    filled[cur] = true;
                    last = cur;
     
                    s.erase(s.begin());
                }
     
                cout << last << '\n';
     
            }else{
                cout << query(k) << '\n';
     
                s.insert({order[k], k});
                filled[k] = false;
            }
        }
     
        return 0;
    }

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 30 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.6666666666666667 / 5