Submission #1086108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086108		Ibrohim0704	Closing Time (IOI23_closing)	C++17	100 / 100	366 ms	57076 KiB

closing

#include "closing.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
vector<pair<int, int>> adj[200005];
int32_t solve1234(int32_t n, int32_t X, int32_t Y, int k) {
    int ans = 0;
    vector<int> vis(n, 0), distx(n, -1), disty(n, -1);
    set<tuple<int, int, int>> pq; // let 0 be x, 1 be y
    distx[X] = 0;
    disty[Y] = 0;
    pq.insert({0, X, 0});
    pq.insert({0, Y, 1});
    while(!pq.empty()) {
        auto [d, a, ind] = *pq.begin();
        pq.erase(*pq.begin());
        if (vis[a] == 0 && distx[a] != -1 && disty[a] != -1) {
            if (ind == 0) {
                if (pq.count({disty[a], a, 1})) {
                    pq.erase({disty[a], a, 1});
                    pq.insert({disty[a]-distx[a], a, 1});
                }
            } else {
                if (pq.count({distx[a], a, 0})) {
                    pq.erase({distx[a], a, 0});
                    pq.insert({distx[a]-disty[a], a, 0});
                }
            }
        }
        vis[a] = d;
        if (k < d) {
            break;
        } else {
            k -= d;
            ans++;
        }
        if (ind == 0) {
            for (auto [b, w] : adj[a]) {
                if (distx[b] != -1) {
                    continue;
                }
                distx[b] = distx[a]+w;
                if (vis[b] >= distx[b]) {
                    pq.insert({0, b, 0});
                } else {
                    pq.insert({(distx[b]-vis[b]), b, 0});
                }
            }
        } else {
            for (auto [b, w] : adj[a]) {
                if (disty[b] != -1) {
                    continue;
                }
                disty[b] = disty[a]+w;
                if (vis[b] >= disty[b]) {
                    pq.insert({0, b, 1});
                } else {
                    pq.insert({(disty[b]-vis[b]), b, 1});
                }
            }
        }
    }
    return ans;
}
int32_t max_score(int32_t n, int32_t X, int32_t Y, int k, vector<int32_t> U, vector<int32_t> V, vector<int32_t> W) {
    int ans = 0, temp = 0;
    vector<int> vis(n, 0), distx(n, -1), disty(n, -1), csing(n, 0), cmult(n, 0);
    for (int i = 0; i < n; i++) {
        adj[i].clear();
    }
    for (int i = 0; i < n-1; i++) {
        adj[U[i]].push_back({V[i], W[i]});
        adj[V[i]].push_back({U[i], W[i]});
    }
    temp = solve1234(n, X, Y, k); // subtask 1, 2, 3, 4, it works
    multiset<pair<int, int>> pq, pqex, pqf; // for normal, for disgusting cases, for last check 
    distx[X] = 0;
    disty[Y] = 0;
    queue<int> q;
    q.push(X);
    while(!q.empty()) {
        int a = q.front();
        q.pop();
        for (auto [b, w] : adj[a]) {
            if (distx[b] == -1) {
                distx[b] = distx[a]+w;
                q.push(b);
            }
        }
    }
    q.push(Y);
    while(!q.empty()) {
        int a = q.front();
        q.pop();
        for (auto [b, w] : adj[a]) {
            if (disty[b] == -1) {
                disty[b] = disty[a]+w;
                q.push(b);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        csing[i] = min(distx[i], disty[i]); // x take or y take
        cmult[i] = max(distx[i], disty[i])-csing[i]; // both take
    }
    // best is to take all on path except not but that is checked by my 1st attempt
    for (int i = 0; i < n; i++) {
        if (distx[i]+disty[i] == distx[Y]) {
            k -= csing[i];
            ans++;
            pq.insert({cmult[i], i});
        }
    }
    if (k <= 0) {
        return temp;
    }
    for (int i = 0; i < n; i++) {
        if (distx[i]+disty[i] == distx[Y]) {
            continue;
        }
        if (csing[i] > cmult[i]) {
            pqex.insert({csing[i]+cmult[i], i});
            pqf.insert({csing[i], i});
        } else {
            pq.insert({csing[i], i});
            pq.insert({cmult[i], i});
        }
    }
    while(pq.size() > 1 && !pqex.empty()) {
        auto [c, i3] = *pqex.begin();
        pqex.erase(pqex.begin());
        auto [a, i1] = *pq.begin();
        pq.erase(pq.begin());
        auto [b, i2] = *pq.begin();
        pq.erase(pq.begin());
        if (c > k) {
            pq.insert({a, i1});
            pq.insert({b, i2});
            pqex.insert({c, i3});
            break;
        }
        if (a+b < c) {
            k -= a;
            ans++;
            pq.insert({b, i2});
            pqex.insert({c, i3});
        } else {
            k -= c;
            vis[i3] = 1;
            ans += 2;
            pq.insert({a, i1});
            pq.insert({b, i2});
        }
    }
    while(!pqex.empty()) {
        auto [a, i1] = *pqex.begin();
        pqex.erase(pqex.begin());
        if (a > k) {
            break;
        } else {
            k -= a;
            vis[i1] = 1;
            ans += 2;
        }
    }
    while(!pq.empty()) {
        auto [a, i1] = *pq.begin();
        pq.erase(pq.begin());
        if (a > k) {
            break;
        } else {
            k -= a;
            ans++;
        }
    }
    while(!pqf.empty()) {
        auto [a, i1] = *pqf.begin();
        pqf.erase(pqf.begin());
        if (vis[i1]) {
            continue;
        }
        if (a > k) {
            break;
        } else {
            k -= a;
            ans++;
        }
    }
    return max(temp, ans);
}

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