oj.uz

Submission #628746

# Submission time Handle Problem Language Result Execution time Memory
628746 2022-08-13T16:26:13 Z bojackduy Toll (BOI17_toll) C++14
18 / 100
 3000 ms 5888 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) {
                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 Execution timed out 3056 ms 4768 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 4452 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 2 ms 2644 KB Output is correct
4 Correct 2 ms 2680 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 4 ms 2772 KB Output is correct
8 Correct 5 ms 2896 KB Output is correct
9 Correct 27 ms 4540 KB Output is correct
10 Correct 51 ms 5612 KB Output is correct
11 Correct 35 ms 4680 KB Output is correct
12 Correct 34 ms 4476 KB Output is correct
13 Correct 57 ms 5668 KB Output is correct
14 Correct 34 ms 4600 KB Output is correct
15 Correct 35 ms 4164 KB Output is correct
16 Correct 27 ms 4236 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2676 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 4 ms 2644 KB Output is correct
8 Correct 8 ms 2804 KB Output is correct
9 Correct 8 ms 2772 KB Output is correct
10 Correct 23 ms 4660 KB Output is correct
11 Correct 135 ms 4776 KB Output is correct
12 Correct 189 ms 5584 KB Output is correct
13 Correct 261 ms 5888 KB Output is correct
14 Correct 183 ms 5196 KB Output is correct
15 Correct 142 ms 4328 KB Output is correct
16 Correct 115 ms 4324 KB Output is correct

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2676 KB Output is correct
4 Correct 2 ms 2676 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 4 ms 2644 KB Output is correct
8 Correct 8 ms 2804 KB Output is correct
9 Correct 8 ms 2772 KB Output is correct
10 Correct 23 ms 4660 KB Output is correct
11 Correct 135 ms 4776 KB Output is correct
12 Correct 189 ms 5584 KB Output is correct
13 Correct 261 ms 5888 KB Output is correct
14 Correct 183 ms 5196 KB Output is correct
15 Correct 142 ms 4328 KB Output is correct
16 Correct 115 ms 4324 KB Output is correct
17 Execution timed out 3051 ms 4772 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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