oj.uz

Submission #1052810

# Submission time Handle Problem Language Result Execution time Memory
1052810 2024-08-11T01:19:19 Z gyg Toll (BOI17_toll) C++17
0 / 100
 3000 ms 101576 KB 
#pragma GCC optimize("Ofast", "unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAX_N = 5e4 + 5, SQRT = 1e2, INF = 1e9;

int k, n, m, q;
array<vector<pii>, MAX_N> adj;

map<int, int> dist;
set<int> seen;
priority_queue<pii, vector<pii>, greater<pii>> order;
void dijk(int s, bool halt = false) {
    dist.clear(), seen.clear();
    dist[s] = 0, order.push({0, s});
    while (order.size()) {
        int u = order.top().second;
        order.pop();
        if (halt && (u / k) % SQRT == 0) continue;

        if (seen.count(u)) continue;
        seen.insert(u);

        for (pii x : adj[u]) {
            int new_dist = dist[u] + x.second;
            if (dist.count(x.first) && new_dist >= dist[x.first]) continue;
            dist[x.first] = new_dist;
            order.push({new_dist, x.first});
        }
    }
}

map<int, array<int, MAX_N>> sp;
void precomp() {
    for (int u = 0; u < n; u++) {
        if ((u / k) % SQRT != 0) continue;
        dijk(u);
        for (int v = 0; v < n; v++)
            sp[u][v] = (dist.count(v)) ? dist[v] : INF;
    }
}

int comp(int s, int f) {
    dijk(s, true);
    
    int ans = INF;
    if (dist.count(f)) ans = min(ans, dist[f]);
    for (pii x : dist)
        if ((x.first / k) % SQRT == 0)
            ans = min(ans, x.second + sp[x.first][f]);

    return ans;
}

int main() {
    // freopen("toll.in", "r", stdin);
    cin >> k >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
    }

    precomp();

    for (int i = 1; i <= q; i++) {
        int s, f; cin >> s >> f;
        int ans = comp(s, f);
        cout << ((ans >= INF) ? -1 : ans) << '\n';
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 49752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3045 ms 75064 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 2168 KB Output is correct
4 Correct 1 ms 2340 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 6 ms 3676 KB Output is correct
8 Correct 25 ms 3672 KB Output is correct
9 Correct 16 ms 3928 KB Output is correct
10 Correct 1328 ms 101576 KB Output is correct
11 Execution timed out 3033 ms 34344 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 2168 KB Output is correct
4 Correct 1 ms 2340 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 3420 KB Output is correct
7 Correct 6 ms 3676 KB Output is correct
8 Correct 25 ms 3672 KB Output is correct
9 Correct 16 ms 3928 KB Output is correct
10 Correct 1328 ms 101576 KB Output is correct
11 Execution timed out 3033 ms 34344 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 49752 KB Time limit exceeded
2 Halted 0 ms 0 KB -