Submission #1266793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266793		rexdino	Toll (BOI17_toll)	C++20	100 / 100	52 ms	8816 KiB

toll

#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define REP(i,a,b) for(int i=(a); i>=(b); --i)
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define sz(v) (int)(v).size()
#define ALL(v) (v).begin(),(v).end()
#define printArr(a, n) for (int i=1; i<=n; ++i) cout << a[i] << " "; el;
#define el cout << "\n"
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N = 5e4 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const ll INF = 1e18;

/// REXDINO FROM LTV HSGS ///
int n, m, k, q;
vector<pii> adj[N];
ll f[6][N], g[6][N], ans[N];

struct Query{
    int u, v, id;
};

void DnC(int l, int r, vector<Query> &qr){
    if (l == r) {
        for (Query T : qr) ans[T.id] = -1;
        return;
    }

    int mid = (l + r) >> 1;

    int L = l * k, R = min(n - 1, (r + 1) * k - 1);

    FOR(i, L, (mid + 1) * k - 1){
        FOR(t, 0, k) f[t][i] = INF;
        if (i / k == mid) f[i % k][i] = 0;
    }

    REP(i, (mid + 1) * k - 1, L){
        for (pii e : adj[i]){
            if (e.fi > (mid + 1) * k - 1) continue;
            FOR(t, 0, k - 1) f[t][i] = min(f[t][i], f[t][e.fi] + e.se);
        }
    }


    FOR(i, (mid + 1) * k, R){
        FOR(t, 0, k) g[t][i] = INF;
        if (i / k == mid + 1) g[i % k][i] = 0;
    }

    FOR(i, (mid + 1) * k, R){
        for (pii e : adj[i]){
            if (e.fi > R) continue;
            FOR(t, 0, k - 1) g[t][e.fi] = min(g[t][e.fi], g[t][i] + e.se);
        }
    }


    vector<Query> vec[2];

    for (Query T : qr){
        int u = T.u, v = T.v;
        ans[T.id] = INF;
        if (u == v) ans[T.id] = -1;
        if (v / k <= mid) vec[0].push_back(T);
        else if (u / k > mid) vec[1].push_back(T);
        else {
            FOR(t, 0, k - 1) if (f[t][u] < INF) {
                for (pii e : adj[mid * k + t]){
                    ans[T.id] = min(ans[T.id], f[t][u] + e.se + g[e.fi % k][v]);
                }
            }

            if (ans[T.id] >= INF) ans[T.id] = -1;
        }

    }

    DnC(l, mid, vec[0]);
    DnC(mid + 1, r, vec[1]);
}


void solve(){
    cin >> k >> n >> m >> q;

    FOR(i, 1, m){
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    vector<Query> vec;
    FOR(i, 1, q){
        int u, v;
        cin >> u >> v;
        vec.push_back({u, v, i});
    }

    DnC(0, (n - 1) / k, vec);

    FOR(i, 1, q) cout << ans[i], el;
}

signed main(){
    #define NAME "main"
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

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

    return 0;
}

Compilation message (stderr)

toll.cpp: In function 'int main()':
toll.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |         freopen(NAME".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
toll.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen(NAME".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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