Submission #1264941

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264941		icebear	Toll (BOI17_toll)	C++20	100 / 100	338 ms	15208 KiB

toll

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;
#define int ll
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 50000 + 5;
int n, k, m, q;
vector<ii> G[2][N];
ll dist[2][6][N], ans[N];
vector<array<int, 3>> queries;

void dijkstra(int T, int layer, int L, int R) {
    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> Q;
    REP(j, k) FOR(i, L * k, min(n, (R + 1) * k) - 1) 
        dist[T][j][i] = INF;
    FOR(i, layer * k, min(n, (layer + 1) * k) - 1) {
        dist[T][i - layer * k][i] = 0;
        Q.push({0, i - layer * k, i});
    }

    while(!Q.empty()) {
        ll du = Q.top()[0]; int u = Q.top()[2], t = Q.top()[1];
        Q.pop();
        if (du != dist[T][t][u]) continue;
        for(ii v : G[T][u]) if (L * k <= v.fi && v.fi < (R + 1) * k) {
            if (minimize(dist[T][t][v.fi], du + v.se))
                Q.push({dist[T][t][v.fi], t, v.fi});
        }
    }
}

void DnC(int L, int R, vector<array<int, 3>> &queries) {
    if (L + 1 >= R) {
        for(auto &x : queries) {
            for(ii v : G[0][x[0]]) if (v.fi == x[1])
                ans[x[2]] = v.se;
        }
        return;
    }
    int mid = (L + R) >> 1;
    vector<array<int, 3>> left, right;
    dijkstra(0, mid, L, R);
    dijkstra(1, mid, L, R);
    for(auto &x : queries) {
        if (x[1] / k <= mid) left.pb(x);
        else if (x[0] / k >= mid) right.pb(x);
        else {
            REP(i, k)   
                minimize(ans[x[2]], dist[1][i][x[0]] + dist[0][i][x[1]]);
        }
    }
    DnC(L, mid, left);
    DnC(mid, R, right);
}

void init(void) {
    cin >> k >> n >> m >> q;
    FOR(i, 1, m) {
        int a, b, t;
        cin >> a >> b >> t;
        G[0][a].pb(mp(b, t));
        G[1][b].pb(mp(a, t));
    }
    FOR(i, 1, q) {
        int a, b;
        cin >> a >> b;
        queries.pb({a, b, i});
    }
}

void process(void) {
    FOR(i, 1, q) ans[i] = INF;
    DnC(0, n / k, queries);
    FOR(i, 1, q) cout << (ans[i] == INF ? -1 : ans[i]) << '\n';
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    int tc = 1;
//     cin >> tc;
    while(tc--) {
        init();
        process();
    }
    return 0;
}

Compilation message (stderr)

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

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