Submission #354306

#	Time	Username	Problem	Language	Result	Execution time	Memory
354306		parsabahrami	Toll (BOI17_toll)	C++17	100 / 100	170 ms	29036 KiB

toll

// Call my Name and Save me from The Dark
#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

const int N = 5e4 + 10, MOD = 1e9 + 7;
int M[N], dp[18][5][N], n, k, q, m; vector<pii> in[N], out[N];

void divide(int l = 0, int r = (n - 1) / k + 1, int h = 0) {
    if (r - l < 3) return;
    int mid = (l + r) >> 1;
    //printf("l %d mid %d r %d\n", l, mid, r);
    for (int i = mid * k; i < mid * k + k; i++) dp[h][i % k][i] = 0;
    for (int i = mid * k - 1; i >= l * k; i--) {
        for (int j = 0; j < k; j++) for (pii u : out[i]) {
            dp[h][j][i] = min(dp[h][j][i], dp[h][j][u.F] + u.S);
        }
    }
    for (int i = mid * k + k; i < min(n, r * k); i++) {
        for (int j = 0; j < k; j++) for (pii u : in[i]) {
            dp[h][j][i] = min(dp[h][j][i], dp[h][j][u.F] + u.S);
        }
    }
    for (int i = mid; i < r; i++) M[i] ^= 1 << h;
    divide(l, mid, h + 1), divide(mid, r, h + 1);
}

int main() {
    for (int i = 0; i < 18; i++) for (int j = 0; j < 5; j++) fill(dp[i][j], dp[i][j] + N, MOD);
    scanf("%d%d%d%d", &k, &n, &m, &q);
    for (int i = 0; i < m; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        out[u].push_back({v, w});
        in[v].push_back({u, w});
    }
    divide();
    for (; q; q--) {
        int a, b; scanf("%d%d", &a, &b);
        if (a == b) printf("%d\n", 0);
        else if (a / k == b / k) printf("-1\n");
        else if (b / k - a / k == 1) {
            int ret = -1;
            for (pii u : out[a])  if (u.F == b) ret = u.S;
            printf("%d\n", ret);
        } else {
            if (M[a / k] == M[b / k]) {
                printf("%d %d\n", a / k, b / k);
                exit(0);
            }
            int h = __builtin_ctz(M[a / k] ^ M[b / k]);
            int ret = MOD;
            for (int i = 0; i < 5; i++) {
                ret = min(ret, dp[h][i][a] + dp[h][i][b]);
            }
            printf("%d\n", ret == MOD ? -1 : ret);
        }
    }
    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:37:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   37 |     scanf("%d%d%d%d", &k, &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:39:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |         int u, v, w; scanf("%d%d%d", &u, &v, &w);
      |                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~
toll.cpp:45:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |         int a, b; scanf("%d%d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~

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