Submission #553119

#	Time	Username	Problem	Language	Result	Execution time	Memory
553119		Talha_Taki	Toll (BOI17_toll)	C++17	100 / 100	234 ms	23336 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);

    const int INF = 1e9;
    int k, n, m, o, group;
    cin >> k >> n >> m >> o;
    group = n/k;

    vector <int> lg(group+1);
    lg[1] = 0;
    for(int i = 2; i <= group; ++i) {
        lg[i] = lg[i>>1] + 1;
    }
    vector <vector <vector <vector <int>>>> dp(group+1, vector <vector <vector <int>>> (k, vector <vector <int>> (k, vector <int> (lg[group]+1, INF))));

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

    for(int l = 1; l <= lg[group]; ++l) {
        for(int i = 0; i <= group; ++i) {
            for(int y = 0; y < k; ++y) {
                for(int z = 0; z < k; ++z) {
                    for(int mid = 0; mid < k; ++mid) {
                        int next = i + (1<<(l-1));
                        if (next > group) continue;
                        dp[i][y][z][l] = min(dp[i][y][z][l], dp[i][y][mid][l-1] + dp[next][mid][z][l-1]);
                    }
                }
            }
        }
    }

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

        int group_a = a/k;
        int group_b = b/k;
        int left = group_b - group_a;
        int source = a % k;
        int destination = __builtin_popcount(left)*k + b % k;
        int node_cnt = (__builtin_popcount(left) + 1) * k;

        vector <vector <pii>> adj(node_cnt);
        vector <int> indegree(node_cnt, 0);

        int ptr = 0;
        for(int l = lg[group]; l >= 0; --l) {
            if ((1<<l) <= left) {
                left -= (1<<l);
                for(int y = 0; y < k; ++y) {
                    int u = ptr*k + y;
                    for(int z = 0; z < k; ++z) {
                        int v = (ptr+1)*k + z;
                        assert(v < node_cnt);
                        adj[u].push_back({v, dp[group_a][y][z][l]});
                        indegree[v]++;
                    }
                }
                group_a += (1<<l);
                ptr++;
            }
        }

        queue <int> Q;
        vector <int> dist(node_cnt, INF);

        for(int i = 0; i < k; ++i) Q.push(i);
        dist[source] = 0;

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

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

                dist[v] = min(dist[v],  dist[u] + w);
                indegree[v]--;

                if (indegree[v] == 0) Q.push(v);
            }
        }

        cout << (dist[destination] == INF? -1LL:dist[destination]) << '\n';
    }


    return 0;
}

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