oj.uz

Submission #628751

# Submission time Handle Problem Language Result Execution time Memory
628751 2022-08-13T16:28:21 Z bojackduy Toll (BOI17_toll) C++14
10 / 100
 67 ms 5560 KB 
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<ll, int> pli;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
const int N = 1e5 + 1;
const int inf = 1e9;
int k, n, m, q;
vii a[N];
pii b[N];
void subtask1() {
        vi d(n + 1, inf);
        priority_queue<pii, vector<pii>, greater<pii> > kew;
        kew.push(pii(0, 0));
        d[0] = 0;
        while (kew.size()) {
            int u = kew.top().se;
            ll du = kew.top().fi;
            kew.pop();
            if (du > d[u]) continue;
            for (pii v: a[u]) {
                if (d[v.se] > du + v.fi) {
                    d[v.se] = du + v.fi;
                    kew.push(pii(d[v.se], v.se));
                }
            }
        }
        for (int i = 1; i <= q; i++) {
            int x, y;
            x = b[i].fi;
            y = b[i].se;
            if (x > y || d[x] == inf || d[y] == inf) {
                cout << "-1\n";
                continue;
            }
            cout << d[y] - (x <= 0 ? 0 : d[x - 1]) << '\n';
        }
}
 
void subtask2() {
    vi d(n + 1, inf);
    priority_queue<pii, vector<pii>, greater<pii>> kew;
    kew.push(pii(0, 0));
    d[0] = 0;
    while (!kew.empty()) {
        int u = kew.top().se;
        int du = kew.top().fi;
        kew.pop();
        if (du > d[u]) continue;
        for (pii v: a[u]) {
            if (d[v.se] > du + v.fi) {
                d[v.se] = du + v.fi;
                kew.push(pii(d[v.se], v.se));
            }
        }
    }
    for (int i = 1; i <= q; i++) {
        cout << (d[b[i].se] == inf ? -1 : d[b[i].se]) << '\n';
    }
}
void subtask3() {
    for (int i = 1; i <= q; i++) {
        int x, y;
        x = b[i].fi;
        y = b[i].se;
        vi d(n + 1, inf);
        priority_queue<pii, vector<pii>, greater<pii>> kew;
        kew.push(pii(0, x));
        d[x] = 0;
        while (kew.size()) {
            int u = kew.top().se;
            int du = kew.top().fi;
            if (u == y) {
                cout << d[u] << '\n';
            break;
            }
            kew.pop();
            if (du > d[u]) continue;
            for (pli v: a[u]) {
                if (d[v.se] > du + v.fi) {
                    d[v.se] = du + v.fi;
                    kew.push(pii(d[v.se], v.se));
                }
            }
        }
        if (d[y] == inf) cout << "-1\n";
    }
}
int32_t main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> k >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        a[x].pb(pii(z, y));
    }
    int cnt = 0;
    for (int i = 1; i <= q; i++) {
        cin >> b[i].fi >> b[i].se;
        if (b[i].fi == 0) cnt++;
    }
    if (k == 1) subtask1(); else
    if (cnt == q) subtask2(); else
    subtask3();
    return 0;
}
/*
5 14 5 5
0 5 9
5 12 10
0 7 7
7 12 8
4 7 10
0 12
0 5
0 7
7 12
0 13
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 4504 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 46 ms 4504 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 5 ms 2820 KB Output is correct
8 Correct 4 ms 2772 KB Output is correct
9 Correct 30 ms 4496 KB Output is correct
10 Correct 64 ms 5500 KB Output is correct
11 Correct 46 ms 4564 KB Output is correct
12 Correct 35 ms 4420 KB Output is correct
13 Correct 67 ms 5560 KB Output is correct
14 Correct 44 ms 4440 KB Output is correct
15 Correct 42 ms 4044 KB Output is correct
16 Correct 40 ms 4076 KB Output is correct

Subtask #3
0 / 8.0

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

Subtask #4
0 / 31.0

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

Subtask #5
0 / 44.0

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