Submission #988667

#	Time	Username	Problem	Language	Result	Execution time	Memory
988667		helloOj	Closing Time (IOI23_closing)	C++17	8 / 100	146 ms	29600 KiB

closing

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <tuple>
#include <functional>
#include <numeric>
#include <limits>

using namespace std;

struct Graph {
protected:
    vector<vector<pair<int, long long>>> edges;
    vector<long long> low, high, distToX, distToY;
    vector<int> path;
    int N, X, Y;
    long long K;
    long long tempK;
    int tempScore, score;
    vector<bool> inOverlap, inLowHeap;
    vector<int> inOutsideHeapCount;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>> OverlapHeap;
    stack<int> lowHeap;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> OutsideHeap;

public:
    Graph(int n, int x, int y, long long k) : N(n), X(x), Y(y), edges(n), K(k), low(n), high(n), distToX(n), distToY(n), inOverlap(n, false), inLowHeap(n, false), inOutsideHeapCount(n, 0), tempK(0), tempScore(0), score(-1) {}


    void build_edge(const vector<int> & u, const vector<int> & v , const vector<int> & w) {
        for(int i = 0; i < N-1; i++){
            addEdge(u[i], v[i], w[i]);
        }
    }

    int findMaxScore() {
        initialize();
        if (!initLowHeap()) return score;
        initOutsideHeap();
        while (refreshScore());
        return score;
    }

protected:
    void addEdge(int u, int v, long long w) {
        edges[u].emplace_back(v, w);
        edges[v].emplace_back(u, w);
    }

    vector<long long> bfs(int start) {
        vector<long long> dist(N, numeric_limits<long long>::max());
        queue<int> q;
        dist[start] = 0;
        q.push(start);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto& [v, w] : edges[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    q.push(v);
                }
            }
        }
        return dist;
    }

    void initialize() {
        distToX = bfs(X);
        distToY = bfs(Y);
        for (int i = 0; i < N; ++i) {
            low[i] = min(distToX[i], distToY[i]);
            high[i] = max(distToX[i], distToY[i]);
        }
        findPath();
    }

    void findPath() {
        vector<int> prev(N, -1);
        queue<int> q;
        q.push(X);
        vector<bool> visited(N, false);
        visited[X] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (u == Y) break;
            for (auto& [v, w] : edges[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    prev[v] = u;
                    q.push(v);
                }
            }
        }
        for (int at = Y; at != -1; at = prev[at]) {
            path.push_back(at);
        }
        reverse(path.begin(), path.end());
    }

    bool initLowHeap() {
        vector<int> lowSort(N);
        iota(lowSort.begin(), lowSort.end(), 0);
        sort(lowSort.begin(), lowSort.end(), [this](int a, int b) { return low[a] < low[b]; });
        for (int node : path) {
            inLowHeap[node] = true;
        }
        long long sumLows = 0;
        int count = 0;
        for (int idx : lowSort) {
            if (sumLows + low[idx] > K) break;
            sumLows += low[idx];
            count++;
        }
        score = count;
        tempK = tempScore = 0;
        for (int node : path) {
            tempK += low[node];
            tempScore++;
        }
        if (tempK >= K) return false;
        for (int i : lowSort) {
            if (!inLowHeap[i] && tempK + low[i] <= K) {
                lowHeap.push(i);
                inLowHeap[i] = true;
                tempK += low[i];
                tempScore++;
            }
        }
        return true;
    }

    void initOutsideHeap() {
        for (int i = 0; i < N; ++i) {
            inOutsideHeapCount[i] = 1;
            if (inLowHeap[i]) {
                OutsideHeap.push({high[i] - low[i], i});
            } else {
                OutsideHeap.push({high[i], i});
            }
        }
    }

    bool refreshScore() {
        if (lowHeap.empty()) return false;
        int u = lowHeap.top();
        lowHeap.pop();
        if (inOverlap[u]) {
            OverlapHeap.push({high[u], u});
        } else {
            tempScore--;
            tempK -= low[u];
            inLowHeap[u] = false;
            OutsideHeap.push({high[u], u});
            inOutsideHeapCount[u]++;
        }
        while (!OutsideHeap.empty() && !OverlapHeap.empty()) {
            auto [costs, s] = OutsideHeap.top();
            auto [costt, t] = OverlapHeap.top();
            if (costs < costt) {
                tempK -= (costt - costs);
                OutsideHeap.pop();
                OverlapHeap.pop();
                inOverlap[t] = false;
                OutsideHeap.emplace(costt, t);
                OverlapHeap.emplace(costs, s);
                inOverlap[s] = true;
            } else {
                break;
            }
        }
        while (!OutsideHeap.empty() && tempK + OutsideHeap.top().first <= K) {
            auto [costs, s] = OutsideHeap.top();
            tempK += costs;
            OutsideHeap.pop();
            OverlapHeap.push({costs, s});
            inOverlap[s] = true;
        }
        score = max(score, tempScore);
        return true;
    }
};

int max_score(int N , int X , int Y , long long K , vector<int> u , vector<int> v , vector<int> w){
    Graph g(N, X, Y, K);
    g.build_edge(u, v, w);
    return g.findMaxScore();
}

Compilation message (stderr)

closing.cpp: In constructor 'Graph::Graph(int, int, int, long long int)':
closing.cpp:17:15: warning: 'Graph::Y' will be initialized after [-Wreorder]
   17 |     int N, X, Y;
      |               ^
closing.cpp:14:42: warning:   'std::vector<std::vector<std::pair<int, long long int> > > Graph::edges' [-Wreorder]
   14 |     vector<vector<pair<int, long long>>> edges;
      |                                          ^~~~~
closing.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     Graph(int n, int x, int y, long long k) : N(n), X(x), Y(y), edges(n), K(k), low(n), high(n), distToX(n), distToY(n), inOverlap(n, false), inLowHeap(n, false), inOutsideHeapCount(n, 0), tempK(0), tempScore(0), score(-1) {}
      |     ^~~~~
closing.cpp:18:15: warning: 'Graph::K' will be initialized after [-Wreorder]
   18 |     long long K;
      |               ^
closing.cpp:15:23: warning:   'std::vector<long long int> Graph::low' [-Wreorder]
   15 |     vector<long long> low, high, distToX, distToY;
      |                       ^~~
closing.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     Graph(int n, int x, int y, long long k) : N(n), X(x), Y(y), edges(n), K(k), low(n), high(n), distToX(n), distToY(n), inOverlap(n, false), inLowHeap(n, false), inOutsideHeapCount(n, 0), tempK(0), tempScore(0), score(-1) {}
      |     ^~~~~
closing.cpp:22:17: warning: 'Graph::inOutsideHeapCount' will be initialized after [-Wreorder]
   22 |     vector<int> inOutsideHeapCount;
      |                 ^~~~~~~~~~~~~~~~~~
closing.cpp:19:15: warning:   'long long int Graph::tempK' [-Wreorder]
   19 |     long long tempK;
      |               ^~~~~
closing.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     Graph(int n, int x, int y, long long k) : N(n), X(x), Y(y), edges(n), K(k), low(n), high(n), distToX(n), distToY(n), inOverlap(n, false), inLowHeap(n, false), inOutsideHeapCount(n, 0), tempK(0), tempScore(0), score(-1) {}
      |     ^~~~~

• 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