Submission #1046981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046981		Esgeer	Toll (BOI17_toll)	C++17	100 / 100	66 ms	167764 KiB

toll

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma optimize("O2")
using namespace __gnu_pbds;
using namespace std;
#define int long long 
#define vi vector<int>
#define vvi vector<vi>
#define sp << " " <<
#define F(i, s, e) for(int i = s; i < e; i++)
#define R(i, s, e) for(int i = s; i >= e; i--)
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define vb vector<bool>
#define endl '\n'
#define Tree tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>
#define vpi vector<pii>

const int N = 5e4 + 5;
const int mod = 1e9 + 7;
const int inf = 1e15;

int dat[16][N][5][5], mask[N];
int k, n, m, q;
vvi go(N, vi(5, inf)), rgo(N, vi(5, inf));

void divi(int l, int r, int layer) {
    if(l == r) return;
    // calculate middle
    int mid = (l + r) >> 1;
    // calculate dat

    // base cases
    F(i, 0, k) {
        dat[layer][mid][i][i] = 0;
    }

    F(i, mid+1, r+1) {
        F(to, 0, k) {
            F(from, 0, k) {
                F(middle, 0, k) {
                    if(rgo[i*k+to][middle] < inf) dat[layer][i][from][to] = min(dat[layer][i][from][to], \
                    dat[layer][i-1][from][middle] + rgo[i*k+to][middle]);
                }
            }
        }
    }
    R(i, mid-1, l) {
        F(to, 0, k) {
            F(from, 0, k) {
                F(middle, 0, k) {
                    if(go[i*k+from][middle] < inf) dat[layer][i][from][to] = min(dat[layer][i][from][to], \
                    dat[layer][i+1][middle][to] + go[i*k+from][middle]);
                }
            }
        }
    }

    // calculate mask
    F(i, mid+1, r+1) {
        mask[i] |= (1 << layer);
    }
    // branch into left and right segments
    divi(l, mid, layer + 1);
    divi(mid+1, r, layer + 1);
}

void solve() {
    F(i, 0, 16) F(j, 0, N) F(k, 0, 5) F(l, 0, 5) dat[i][j][k][l] = inf;
    cin >> k >> n >> m >> q;

    F(i, 0, m) {
        int u, v, w;
        cin >> u >> v >> w;
        if(u > v) swap(u, v);

        go[u][v % k] = w;
        rgo[v][u % k] = w;
    }

    int blockSize = (n + k - 1) / k;

    divi(0, blockSize - 1, 0);

    F(i, 0, q) {
        int u, v;
        cin >> u >> v;
        int lu = u / k, lv = v / k;
        if(u == v) cout << 0 << endl;
        else if(lu >= lv) {
            cout << -1 << endl;
        } else {
            int level = __builtin_ctz(mask[lu] ^ mask[lv]);

            int mn = inf;
            F(middle, 0, k) {
                mn = min(mn, dat[level][lu][u % k][middle] + dat[level][lv][middle][v % k]);
            }

            if(mn < inf) cout << mn << endl;
            else cout << -1 << endl;
        }
    }
}

int32_t main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    #ifdef Local
        freopen("io.in", "r", stdin);
        freopen("io.out", "w", stdout);
    #endif

    int t = 1;
    //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

toll.cpp:4: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    4 | #pragma optimize("O2")
      |

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