Submission #988665

# Submission time Handle Problem Language Result Execution time Memory
988665 2024-05-25T12:23:16 Z helloOj Closing Time (IOI23_closing) C++17
Compilation error
0 ms 0 KB
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <tuple>
#include <cstdint>
#include <functional>
#include <numeric>
#include <limits>

using namespace std;

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

public:
    Graph(int n, int x, int y, int64_t k) : N(n), X(x), Y(y), K(k), edges(n), 
        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(int *u, int *v, 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, int64_t w) {
        edges[u].emplace_back(v, w);
        edges[v].emplace_back(u, w);
    }

    vector<int64_t> bfs(int start) {
        vector<int64_t> dist(N, numeric_limits<int64_t>::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;
        }
        int64_t 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;
    }
};

Compilation message

closing.cpp: In constructor 'Graph::Graph(int, int, int, int64_t)':
closing.cpp:19:13: warning: 'Graph::K' will be initialized after [-Wreorder]
   19 |     int64_t K;
      |             ^
closing.cpp:15:40: warning:   'std::vector<std::vector<std::pair<int, long int> > > Graph::edges' [-Wreorder]
   15 |     vector<vector<pair<int, int64_t>>> edges;
      |                                        ^~~~~
closing.cpp:29:5: warning:   when initialized here [-Wreorder]
   29 |     Graph(int n, int x, int y, int64_t k) : N(n), X(x), Y(y), K(k), edges(n),
      |     ^~~~~
closing.cpp:23:17: warning: 'Graph::inOutsideHeapCount' will be initialized after [-Wreorder]
   23 |     vector<int> inOutsideHeapCount;
      |                 ^~~~~~~~~~~~~~~~~~
closing.cpp:20:13: warning:   'int64_t Graph::tempK' [-Wreorder]
   20 |     int64_t tempK;
      |             ^~~~~
closing.cpp:29:5: warning:   when initialized here [-Wreorder]
   29 |     Graph(int n, int x, int y, int64_t k) : N(n), X(x), Y(y), K(k), edges(n),
      |     ^~~~~
/usr/bin/ld: /tmp/cc2QWpwc.o: in function `main':
grader.cpp:(.text.startup+0x6a1): undefined reference to `max_score(int, int, int, long long, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status