Submission #464067

#	Time	Username	Problem	Language	Result	Execution time	Memory
464067		deinfreund	Toll (BOI17_toll)	C++17	100 / 100	1032 ms	30992 KiB

toll

#include <bits/stdc++.h>
#define int int64_t

using namespace std;

vector<map<int, int, greater<int>>> graph; // map<target, distance>
int K;
const int INF = 1e10;

int findShortestDistance(int s, int e) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    unordered_map<int, int> distance;
    pq.emplace(0, s);
    while (!pq.empty()){
        auto [cost, pos] = pq.top();
        pq.pop();
        if (distance.find(pos) != distance.end()) continue;
        distance[pos] = cost;
        int k = -1;
        for (const auto& [p, c] : graph[pos]) {
            if (p <= e) { // can't go backwards due to graph structure
                if (k == -1) k = p / K;
                if (k != p / K) break;
                pq.emplace(cost + c, p);
            }
        }
    }
    return distance.find(e) == distance.end() ? INF : distance.at(e);
}

void addSkipEdges(int skipDistance) {
    vector<tuple<int, int, int>> edgesToAdd;
    for (int startCluster = 0; startCluster < graph.size() / K; startCluster+=skipDistance) {
        for (int startNode = startCluster * K; startNode < (startCluster + 1) * K; startNode++) {
            for (int endNode = (startCluster + skipDistance) * K; endNode < (startCluster + skipDistance + 1) * K; endNode++) {
                if (endNode >= graph.size()) break;
                edgesToAdd.emplace_back(startNode, endNode, findShortestDistance(startNode, endNode));
            }
        }
    }
    for (const auto& [startNode, endNode, distance] : edgesToAdd) {
        graph[startNode][endNode] = distance;
    }
}

main() {
    int N,M,O;
    cin >> K >> N >> M >> O;
    graph.resize(N);
    for (int i = 0; i < M; i++) {
        int s, e, c;
        cin >> s >> e >> c;
        graph[s][e] = c;
    }
    for (int skipDist = 1; skipDist < N / K; skipDist *= 2) {
        addSkipEdges(skipDist);
    }
    for (int o = 0; o < O; o++) {
        int s, e;
        cin >> s >> e;
        int dist = findShortestDistance(s, e);
        cout << (dist < INF ? dist : -1) << "\n";
    }
}

Compilation message (stderr)

toll.cpp: In function 'void addSkipEdges(int64_t)':
toll.cpp:33:45: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'long unsigned int' [-Wsign-compare]
   33 |     for (int startCluster = 0; startCluster < graph.size() / K; startCluster+=skipDistance) {
      |                                ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
toll.cpp:36:29: warning: comparison of integer expressions of different signedness: 'int64_t' {aka 'long int'} and 'std::vector<std::map<long int, long int, std::greater<long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |                 if (endNode >= graph.size()) break;
      |                     ~~~~~~~~^~~~~~~~~~~~~~~
toll.cpp: At global scope:
toll.cpp:46:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   46 | main() {
      | ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 8 / 8
• Subtask 4: 31 / 31
• Subtask 5: 44 / 44