oj.uz

Submission #917798

# Submission time Handle Problem Language Result Execution time Memory
917798 2024-01-28T19:40:02 Z VMaksimoski008 Toll (BOI17_toll) C++14
18 / 100
 348 ms 6348 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int k, m, n, o;
vector<vector<pii> > graph;

int32_t main() {
    setIO();

    cin >> k >> n >> m >> o;
    graph.resize(n);

    for(int i=0; i<m; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        graph[a].push_back({ b, w });
    }

    vector<pii> qus;
    int cnt0 = 0;

    for(int i=0; i<o; i++) {
        int a, b;
        cin >> a >> b;
        qus.push_back({ a, b });
        cnt0 += (a == 0);
    }

    vector<ll> dist(n, 1e18);
    vector<bool> vis(n, 0);
    priority_queue<pll, vector<pll>, greater<pll> > pq;

    auto dijkstra = [&](int start) {
        for(int i=0; i<n; i++) dist[i] = 1e18, vis[i] = 0;
        dist[start] = 0;
        pq.push({ 0, start });

        while(!pq.empty()) {
            int u = pq.top().second;
            pq.pop();

            if(vis[u]) continue;
            vis[u] = 1;

            for(auto &[v, w] : graph[u]) {
                if(dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    pq.push({ dist[v], v });
                }
            }
        }
    };

    if(cnt0 == o) {
        dijkstra(0);
        for(auto &x : qus)
            cout << (vis[x.second] ? dist[x.second] : -1) << '\n';
        return 0;
    }

    if(o <= 1000) {
        for(pii &x : qus) {
            dijkstra(x.first);
            cout << (vis[x.second] ? dist[x.second] : -1) << '\n';
        }
        return 0;
    }

    return 0;
}

Compilation message

toll.cpp: In lambda function:
toll.cpp:71:23: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   71 |             for(auto &[v, w] : graph[u]) {
      |                       ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3804 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 4828 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 13 ms 3808 KB Output is correct
10 Correct 40 ms 6096 KB Output is correct
11 Correct 29 ms 4824 KB Output is correct
12 Correct 19 ms 4196 KB Output is correct
13 Correct 49 ms 6232 KB Output is correct
14 Correct 25 ms 3924 KB Output is correct
15 Correct 23 ms 3420 KB Output is correct
16 Correct 20 ms 3420 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 9 ms 664 KB Output is correct
9 Correct 7 ms 348 KB Output is correct
10 Correct 22 ms 3616 KB Output is correct
11 Correct 228 ms 4548 KB Output is correct
12 Correct 297 ms 5976 KB Output is correct
13 Correct 348 ms 6348 KB Output is correct
14 Correct 278 ms 5208 KB Output is correct
15 Correct 190 ms 3264 KB Output is correct
16 Correct 179 ms 3164 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 9 ms 664 KB Output is correct
9 Correct 7 ms 348 KB Output is correct
10 Correct 22 ms 3616 KB Output is correct
11 Correct 228 ms 4548 KB Output is correct
12 Correct 297 ms 5976 KB Output is correct
13 Correct 348 ms 6348 KB Output is correct
14 Correct 278 ms 5208 KB Output is correct
15 Correct 190 ms 3264 KB Output is correct
16 Correct 179 ms 3164 KB Output is correct
17 Incorrect 23 ms 4440 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3804 KB Output isn't correct
2 Halted 0 ms 0 KB -