Submission #840919

#	Time	Username	Problem	Language	Result	Execution time	Memory
840919		nicksms	Closing Time (IOI23_closing)	C++17	43 / 100	207 ms	54184 KiB

closing

#include "closing.h"
/**
 *      Author:  Nicholas Winschel
 *      Created: 08.31.2023 14:51:13
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
#include <vector>

int max_score(int N, int X, int Y, long long K,
              std::vector<int> u, std::vector<int> v, std::vector<int> W)
{
    // assume cannot/optimal not to reach common vertex
    // overestimates cost in the case that it is possible and optimal
    // swap(u,v);
    ll oK = K;
    V<vi> adj(N);
    for (int i = 0; i < N-1; i++) {
        adj[u[i]].push_back(i);
        adj[v[i]].push_back(i);
    }
    struct op {
        ll c;
        int v, p;
        op () {}
        op(ll c, int v, int p) : c(c), v(v), p(p) {}
        bool operator<(const op b) const {
            return c < b.c;
        }
        bool operator>(const op b) const {
            return c > b.c;
        }
    };
    priority_queue<op, V<op>, greater<op>> pq; 
    pq.emplace(0,X,-1);
    pq.emplace(0,Y,-1);
    int ans1 = 0;
    while (sz(pq)) {
        op e = pq.top();
        pq.pop();
        if (e.c > K) continue;
        K -= e.c;
        ans1++;
        for (int i : adj[e.v]) {
            int x = u[i] == e.v ? v[i] : u[i];
            if (x == e.p) continue;
            pq.emplace(e.c+W[i],x,e.v);
        }
    }
    K = oK;
    vl dist1(N), dist2(N);
    auto dfs = [&](int vv, int p, ll d, vl &a, auto &&dfs) -> void {
        a[vv] = d;
        for (int i : adj[vv]) {
            int x = u[i] == vv ? v[i] : u[i];
            if (x == p) continue;
            dfs(x, vv, d+W[i], a, dfs);
        }
    };
    dfs(X, -1, 0, dist1, dfs);
    dfs(Y, -1, 0, dist2, dfs);
    // for (auto x : dist1) cerr << x << " ";
    //cerr << "\n";
    // for (auto x : dist2) cerr << x << " ";
    //cerr << "\n";
    ll btw = dist2[X];
    V<bool> done(2*N);
    using sins = tuple<ll, int, int>; // cost, op, prev
    using dins = tuple<ll, int, int, int>; // cost, op1, op2, prev
    priority_queue<sins, V<sins>, greater<sins>> q1;
    priority_queue<dins, V<dins>, greater<dins>> q2;
    int ans = 0;
    auto perform = [&](int op, int prev) {
        //cerr << "dbg: " << K << " " << op << " " << prev << "\n";
        int vert = op >= N ? op - N : op;
        assert(!done[op]);
        ans++;
        if ((op < N) != (dist1[vert] <= dist2[vert])) { // NO KIDS
            done[op] = true;
        } else {
            done[op] = true;
            ll cu = abs(dist2[vert]-dist1[vert]);
            q1.emplace(cu, N-(op-vert) + vert, vert); // opposite
            bool b = (dist2[vert] >= dist1[vert]);
            for (int i : adj[vert]) {
                int x = u[i] == vert ? v[i] : u[i];
                if (x == prev) continue;
                if ((dist2[x] >= dist1[x]) != b) continue;
                q1.emplace(min(dist1[x], dist2[x]), x + op - vert, vert); // child
                q2.emplace(max(dist1[x], dist2[x]), x, x+N, vert); // both child
                for (int j : adj[x]) { // this is only OK because we are in a tree...
                    int y = u[j] == x ? v[j] : u[j];
                    if (y == vert) continue;
                    if ((dist2[y] >= dist1[y]) != b) continue;
                    q2.emplace(min(dist1[x], dist2[x]) + min(dist1[y], dist2[y]),
                        x + op - vert,
                        y + op - vert,
                        vert);
                }
            }
        }
    };
    for (int i = 0; i < N; i++) {
        if (dist1[i] + dist2[i] == btw) {
            if (dist1[i] <= dist2[i]) {
                K -= dist1[i];
                perform(i, -1);
            } else {
                K -= dist2[i];
                perform(i + N, -1);
            }
        }
    }
    if (K < 0) return ans1;
    //cerr << "???\n";
    //cerr << sz(q1) << " " << sz(q2) << "\n";
    while (sz(q1) || sz(q2)) {
        while (q2.size()) {
            auto [cu, fi, se, pre] = q2.top();
            if (done[fi] || done[se] || cu > K) {
                //cerr << "popping q2: " << cu << " " << fi << " " << se << " " << pre << "\n";
                q2.pop();
                // //cerr << "Popped q2!\n";
            } else break;
        }
        while (q1.size()) {
            auto [cu, op, pre] = q1.top();
            if (done[op] || cu > K) {
                //cerr << "popping q1: " << cu << " " << op << " " << pre << "\n";
                q1.pop();
                // //cerr << "Popped q1!\n";
            } else break;
        }
        //cerr << "body\n";
        if (q1.size() && !q2.size()) {
            //cerr << "path1\n";
            auto [cu, op, pre] = q1.top();
            q1.pop();
            K -= cu;
            perform(op, pre); 
        } else if (q2.size()) {
            //cerr << "path2\n";
            assert(q1.size());
            auto o1 = q1.top();
            q1.pop();
            while (q1.size()) {
                auto [cu, op, pre] = q1.top();
                if (done[op] || cu > K) {
                    q1.pop();
                } else break;
            }
            auto ob = q2.top();
            if (sz(q1)) { // not given
                auto [cu1, op1, pre1] = o1; 
                auto o2 = q1.top();
                auto [cu2, op2, pre2] = o2;
                // q1.pop();
                auto [cub, fi, se, preb] = ob;
                if (cub <= cu1 + cu2) {
                    q2.pop();
                    K -= cub;
                    perform(fi, preb);
                    perform(se, fi >= N ? fi - N : fi);
                    q1.push(o1);
                    // q1.push(o2);
                } else {
                    K -= cu1;
                    perform(op1, pre1);
                    // q1.push(o2);
                    // q2.push(ob);
                }
            } else {
                q1.push(o1);
                auto [cub, fi, se, preb] = ob;
                q2.pop();
                K -= cub;
                perform(fi, preb);
                perform(se, fi >= N ? fi - N : fi);
            }
        }
    }



    return max(ans, ans1);
}

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