Submission #707187

#	Time	Username	Problem	Language	Result	Execution time	Memory
707187		thimote75	Toll (BOI17_toll)	C++14	100 / 100	231 ms	169144 KiB

toll

#include <bits/stdc++.h>

using namespace std;

#define num long long

int nbNodes, nbRoads, bucketSize, nbQuery;
int bucketCount;

#define MAX_BUCKET_SIZE 5
#define MAX_BUCKET_GRID 25

#define LINF 1e17

struct AdjGraph {
    num grid[MAX_BUCKET_SIZE][MAX_BUCKET_SIZE];

    AdjGraph () {
        for (int a = 0; a < bucketSize; a ++)
            for (int b = 0; b < bucketSize; b ++)
                grid[a][b] = LINF;
    }
    void identity () {
        for (int a = 0; a < bucketSize; a ++)
            for (int b = 0; b < bucketSize; b ++)
                grid[a][b] = a == b ? 0 : LINF;
    }

    AdjGraph compile (AdjGraph &other) {
        AdjGraph res;

        for (int a = 0; a < bucketSize; a ++) {
            for (int b = 0; b < bucketSize; b ++) {
                num minValue = LINF;

                for (int i = 0; i < bucketSize; i ++) {
                    minValue = min(
                        minValue,
                        grid[a][i] + other.grid[i][b]
                    );
                }

                res.grid[a][b] = minValue;
            }
        }

        return res;
    }
};

vector<vector<AdjGraph>> displacement_2k;

int getBucket (int node) {
    return node / bucketSize;
}
int getBucketId(int node) {
    return node % bucketSize;
}

AdjGraph compile (int node, int delta) {
    AdjGraph left;
    left.identity();

    int h = displacement_2k[0].size();
    while (h >= 1) {
        h --;
        if (((1 << h) & delta) == 0) continue ;

        left  = left.compile(displacement_2k[node][h]);
        node += 1 << h;
    }

    return left;
}

num solve (int a, int b) {
    int ba = getBucket(a), bb = getBucket(b);

    //bb --;
    AdjGraph graph = compile(ba, bb - ba);

    return graph.grid[getBucketId(a)][getBucketId(b)];
}

int main () {
    cin >> bucketSize >> nbNodes >> nbRoads >> nbQuery;
    bucketCount = nbNodes / bucketSize;

    displacement_2k.resize(bucketCount, vector<AdjGraph>(ceil(log2(bucketCount)) + 1));
    
    for (int idRoad = 0; idRoad < nbRoads; idRoad ++) {
        int a, b;
        cin >> a >> b;

        int ba = getBucket(a);
        int bb = getBucket(b);

        cin >> displacement_2k[ba][0].grid[getBucketId(a)][getBucketId(b)];
    }

    for (int h = 0; h + 1 < displacement_2k[0].size(); h ++) {
        int delta = 1 << h;

        for (int id = 0; id + delta < bucketCount; id ++) {
            displacement_2k[id][h + 1]
             = displacement_2k[id][h].compile(displacement_2k[id + delta][h]);
        }
    }

    for (int q = 0; q < nbQuery; q ++) {
        int a, b;
        cin >> a >> b;

        num res = solve(a, b);
        if (res == LINF) cout << -1 << endl;
        else cout << res << endl;
    }
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:97:13: warning: unused variable 'bb' [-Wunused-variable]
   97 |         int bb = getBucket(b);
      |             ^~
toll.cpp:102:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<AdjGraph>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int h = 0; h + 1 < displacement_2k[0].size(); h ++) {
      |                     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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