Submission #1082006

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082006		LaMatematica14	Closing Time (IOI23_closing)	C++17	8 / 100	1113 ms	533276 KiB

closing

#include <bits/stdc++.h>
using namespace std; 

struct tree {
    vector<vector<array<long long, 2>>> adj;
    void dfs(int ba, vector<long long> &dist, vector<int> &p) {
        for (auto x : adj[ba]) {
            if (x[0] == p[ba]) continue;
            dist[x[0]] = dist[ba]+x[1];
            p[x[0]] = ba;
            dfs(x[0], dist, p);
        }
    }
    queue<int> agg(long long a, vector<int> &re, vector<int> &p) {
        queue<int> t;
        re[a] = 1;
        if (re[p[a]] < 2) return t;
        stack<int> upd; upd.push(a);
        while (!upd.empty()) {
            int n = upd.top(); upd.pop();
            re[n] = 2; t.push(n);
            for (auto x : adj[n]) {
                if (x[0] == p[a]) continue;
                if (re[x[0]] == 0) continue;
                upd.push(x[0]);
            }
        }
        return t;
    }

    int m(int N, int X, int Y, long long K, vector<int> &U, vector<int> &V, vector<int> &W) {
        vector<long long> dx(N, 0);
        vector<long long> dy(N, 0);
        vector<int> px(N, -1);
        vector<int> py(N, -1);
        adj.resize(N);
        for (long long i = 0; i < N-1; i++ ) {
            adj[U[i]].push_back({V[i], W[i]});
            adj[V[i]].push_back({U[i], W[i]});
        }
        
        dfs(X, dx, px);
        dfs(Y, dy, py);

        vector<int> ax(N, 0); vector<int> ay(N, 0); //0 spento, 1 acc, 2 reachable
        priority_queue<array<long long, 3>> d;
        for (long long i = 0; i < N; i++) {
            if (i == X) {
                d.push({-dy[X], X, 1});
                ax[X] = 2;
            }
            else if (i == Y) {
                d.push({-dx[Y], Y, 0});
                ay[Y] = 2;
            }
            else if (dx[i] < dy[i]) d.push({-dx[i], i, 1});
            else d.push({-dy[i], i, 0});
        }

        long long att = 0, k = 2;
        while (k < 2*N && att-d.top()[0] <= K) {
            att -= d.top()[0]; k++;
            auto a = d.top(); d.pop();
            if (a[1] < 0) continue;
            if (a[2]) {
                queue<int> r = agg(a[1], ay, py);
                while (!r.empty()) {
                    d.push({dx[r.front()]-dy[r.front()], -1, 0});
                    r.pop();
                }
            }
            else {
                queue<int> r = agg(a[1], ax, px);
                while (!r.empty()) {
                    d.push({dy[r.front()]-dx[r.front()], -1, 0});
                    r.pop();
                }
            }
        }
        return k;
    }

};

int max_score(int N, int X, int Y, long long K,vector<int> U, vector<int> V, vector<int> W) {
    tree a;
    return a.m(N, X, Y, K, U, V, W);
}

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17