Submission #552886

#	Time	Username	Problem	Language	Result	Execution time	Memory
552886		Talha_Taki	Toll (BOI17_toll)	C++17	0 / 100	89 ms	26636 KiB

toll

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;
typedef pair <int, int> pii;


int main(const int argc, const char *argv[]) {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int k, n, m, o, x;
    cin >> k >> n >> m >> o;
    x = ceil(log2(n));

    const int INF = 1e9;
    vector <vector <vector <int>>> dp(n, vector <vector <int>> (k, vector <int> (x+1, INF)));

    for(int i = 0; i < m; ++i) {
        int a, b, w;
        cin >> a >> b >> w;
        dp[a][b%k][0] = w;
    }

    for(int l = 1; l <= x; ++l) {
        for(int i = 0; i < n; ++i) {
            for(int j = 0; j < k; ++j) {
                for(int z = 0; z < k; ++z) {
                    int mid = (i/k + (1<<(l-1)))*k + z;
                    if (mid >= n) continue;
                    dp[i][j][l] = min(dp[i][j][l], dp[i][z][l-1] + dp[mid][j][l-1]);
                }
            }
        }
    }

    while (o--) {
        int a, b;
        cin >> a >> b;

        int left = b/k - a/k;
        int ptr = 0;
        int node_cnt = (__builtin_popcount(left)) * k + 1;

        vector <vector <pii>> adj(node_cnt);
        vector <int> indegere(node_cnt, 0);
        for(int l = x; l >= 0; --l) {
            if ((1<<l) <= left) {
                left -= (1<<l);
                if (!ptr) {
                    for(int z = 0; z < k; ++z) {
                        adj[0].push_back({z+1, dp[a][z][l]});
                    }
                    a = (a/k + (1<<l))*k;
                }
                else {
                    for(int x = 0; x < k; ++x) {
                        for(int y = 0; y < k; ++y) {
                            adj[(ptr-1)*k + x + 1].push_back({ptr*k + y + 1, dp[a++][y][l]});
                        }
                    }
                }
                a = ((a-1)/k + (1<<l))*k;
                ptr++;
            }
        }

        vector <int> dist(node_cnt, INF);
        dist[0] = 0;

        queue <int> Q;
        Q.push(0);

        while (!Q.empty()) {
            int u = Q.front();
            Q.pop();

            for(auto edge : adj[u]) {
                int v = edge.first;
                int w = edge.second;

                indegere[v]--;
                dist[v] = min(dist[v], dist[u] + w);
                if (indegere[v] == 0) Q.push(v);
            }
        }

        int destination = (ptr-1)*k + (b % k) + 1;
        cout << (destination < 0 || dist[destination] == INF? -1LL:dist[destination]) << '\n';
    }


    return 0;
}

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