Submission #784768

#	Time	Username	Problem	Language	Result	Execution time	Memory
784768		chanhchuong123	Toll (BOI17_toll)	C++14	100 / 100	90 ms	11840 KiB

toll

#pragma GCC optimize("O2")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 7;
const int MAX = 50000;
int k, n, m, q;
int A[MAX], B[MAX];
vector<int> blk[MAX];
int ans[MAX], ID[MAX];
int L[MAX][5], R[MAX][5];
vector<pair<int, int>> go[MAX], back[MAX];

bool minimize(int &x, const int &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}

void divi(int l, int r, vector<int> &v) {
    if (v.empty()) return;
    if (l == r) {
        for (int &id: v) {
            if (A[id] == B[id]) ans[id] = 0;
            else ans[id] = INF;
        }
        return;
    }
    int mid = l + r >> 1;
    int lef = l * k, rig = min(n, r * k + k) - 1;
    for (int i = lef; i <= rig; ++i) {
        for (int t = 0; t < k; ++t) {
            L[i][t] = R[i][t] = INF;
        }
    }
    for (int i = 0; i < blk[mid].size(); ++i) {
        int u = blk[mid][i]; L[u][i] = 0;
        for (pair<int, int> &x: go[u]) {
            int v = x.first, w = x.second;
            R[v][i] = w;
        }
    }
    for (int i = mid; i >= l + 1; --i) {
        for (int &u: blk[i]) {
            for (int t = 0; t < k; ++t) {
                for (pair<int, int> &x: back[u]) {
                    int v = x.first, w = x.second;
                    minimize(L[v][t], L[u][t] + w);
                }
            }
        }
    }
    for (int i = mid + 1; i <= r - 1; ++i) {
        for (int &u: blk[i]) {
            for (int t = 0; t < k; ++t) {
                for (pair<int, int> &x: go[u]) {
                    int v = x.first, w = x.second;
                    minimize(R[v][t], R[u][t] + w);
                }
            }
        }
    }
    vector<int> todo[2];
    for (int &id: v) {
        if (ID[A[id]] <= mid && mid < ID[B[id]]) {
            for (int t = 0; t < k; ++t)
                minimize(ans[id], L[A[id]][t] + R[B[id]][t]);
        } else {
            todo[ID[A[id]] > mid].push_back(id);
        }
    }
    divi(l, mid, todo[0]); divi(mid + 1, r, todo[1]);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cin >> k >> n >> m >> q;
    while (m--) {
        int a, b, t; cin >> a >> b >> t;
        back[b].push_back({a, t});
        go[a].push_back({b, t});
    }
    for (int i = 0; i < n; ++i) {
        ID[i] = i / k;
        blk[ID[i]].push_back(i);
    }
    vector<int> todo;
    for (int i = 0; i < q; ++i) {
        cin >> A[i] >> B[i];
        todo.push_back(i);
    }
    memset(ans, 0x3f, sizeof ans);
    divi(0, (n - 1) / k, todo);
    for (int i = 0; i < q; ++i) {
        if (ans[i] >= INF) cout << "-1\n";
        else cout << ans[i] << '\n';
    }
	return 0;
}

Compilation message (stderr)

toll.cpp: In function 'void divi(int, int, std::vector<int>&)':
toll.cpp:32:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   32 |     int mid = l + r >> 1;
      |               ~~^~~
toll.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < blk[mid].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~~

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