oj.uz

Submission #485473

# Submission time Handle Problem Language Result Execution time Memory
485473 2021-11-08T00:28:10 Z SirCovidThe19th Evacuation plan (IZhO18_plan) C++17
100 / 100
 953 ms 57964 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define pii pair<int, int>
#define f first
#define s second

struct Edge{ int a, b, w; };

const int mx = 1e5 + 5;

int n, m, k, q, dist[mx], par[mx], sz[mx], ans[mx];
vector<Edge> edg; vector<pii> adj[mx]; set<int> qrys[mx];

void dijkstra(){
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    fill(dist, dist + n + 1, 2e9);

    cin >> k;
    FOR(i, 0, k){ int x; cin >> x; dist[x] = 0; pq.push({0, x}); }

    while (!pq.empty()){
        int cdist, cur; tie(cdist, cur) = pq.top(); pq.pop();
        if (dist[cur] != cdist) continue;
        for (pii nxt : adj[cur]){
            int D = cdist + nxt.s;
            if (D < dist[nxt.f]) dist[nxt.f] = D, pq.push({D, nxt.f});
        }
    }
}
int get(int i){ 
    return i == par[i] ? i : par[i] = get(par[i]); 
}
void merge(int a, int b, int w){
    a = get(a); b = get(b); if (a == b) return;
    if (sz[a] > sz[b]) swap(a, b);
    if (qrys[a].size() > qrys[b].size()) swap(qrys[a], qrys[b]);
    par[a] = b; sz[b] += sz[a];
    for (int x : qrys[a]){
        if (qrys[b].count(x)) ans[x] = w, qrys[b].erase(x);
        else qrys[b].insert(x);
    }
}


int main(){
    cin >> n >> m;
    FOR(i, 1, m + 1){
        int a, b, w; cin >> a >> b >> w;
        adj[a].push_back({b, w}); adj[b].push_back({a, w});
        edg.push_back({a, b, w});
    }
    dijkstra();

    cin >> q;
    FOR(i, 1, q + 1){
        int a, b; cin >> a >> b;
        qrys[a].insert(i); qrys[b].insert(i);
    }

    for (Edge &E : edg) E.w = min(dist[E.a], dist[E.b]);
    sort(edg.begin(), edg.end(), [](Edge a, Edge b){ return a.w > b.w; });

    FOR(i, 1, n + 1) par[i] = i, sz[i] = 1;
    for (Edge E : edg) merge(E.a, E.b, E.w);
    
    FOR(i, 1, q + 1) cout<<ans[i]<<endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 6 ms 7500 KB Output is correct
3 Correct 6 ms 7500 KB Output is correct
4 Correct 3 ms 7244 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 7 ms 7500 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 3 ms 7372 KB Output is correct
9 Correct 6 ms 7500 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 6 ms 7492 KB Output is correct
12 Correct 6 ms 7500 KB Output is correct
13 Correct 6 ms 7500 KB Output is correct
14 Correct 6 ms 7500 KB Output is correct
15 Correct 6 ms 7492 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 6 ms 7500 KB Output is correct
3 Correct 6 ms 7500 KB Output is correct
4 Correct 3 ms 7244 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 7 ms 7500 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 3 ms 7372 KB Output is correct
9 Correct 6 ms 7500 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 6 ms 7492 KB Output is correct
12 Correct 6 ms 7500 KB Output is correct
13 Correct 6 ms 7500 KB Output is correct
14 Correct 6 ms 7500 KB Output is correct
15 Correct 6 ms 7492 KB Output is correct
16 Correct 404 ms 26608 KB Output is correct
17 Correct 854 ms 49524 KB Output is correct
18 Correct 63 ms 11056 KB Output is correct
19 Correct 378 ms 26668 KB Output is correct
20 Correct 863 ms 49896 KB Output is correct
21 Correct 593 ms 35036 KB Output is correct
22 Correct 336 ms 26416 KB Output is correct
23 Correct 871 ms 49572 KB Output is correct
24 Correct 890 ms 49536 KB Output is correct
25 Correct 853 ms 49596 KB Output is correct
26 Correct 361 ms 26460 KB Output is correct
27 Correct 368 ms 26616 KB Output is correct
28 Correct 369 ms 26456 KB Output is correct
29 Correct 375 ms 26764 KB Output is correct
30 Correct 364 ms 26580 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 3 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 4 ms 7348 KB Output is correct
5 Correct 4 ms 7344 KB Output is correct
6 Correct 4 ms 7348 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 5 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 4 ms 7372 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 21532 KB Output is correct
2 Correct 551 ms 38836 KB Output is correct
3 Correct 527 ms 38496 KB Output is correct
4 Correct 106 ms 14460 KB Output is correct
5 Correct 529 ms 38472 KB Output is correct
6 Correct 539 ms 38504 KB Output is correct
7 Correct 535 ms 38624 KB Output is correct
8 Correct 528 ms 38500 KB Output is correct
9 Correct 536 ms 38632 KB Output is correct
10 Correct 528 ms 38504 KB Output is correct
11 Correct 554 ms 38472 KB Output is correct
12 Correct 559 ms 38580 KB Output is correct
13 Correct 545 ms 38568 KB Output is correct
14 Correct 549 ms 38696 KB Output is correct
15 Correct 571 ms 39632 KB Output is correct
16 Correct 553 ms 38524 KB Output is correct
17 Correct 557 ms 38700 KB Output is correct
18 Correct 574 ms 38632 KB Output is correct
19 Correct 99 ms 14452 KB Output is correct
20 Correct 547 ms 38504 KB Output is correct
21 Correct 535 ms 38628 KB Output is correct
22 Correct 110 ms 16264 KB Output is correct
23 Correct 112 ms 14892 KB Output is correct
24 Correct 117 ms 16268 KB Output is correct
25 Correct 108 ms 16236 KB Output is correct
26 Correct 112 ms 15144 KB Output is correct
27 Correct 101 ms 14436 KB Output is correct
28 Correct 108 ms 16232 KB Output is correct
29 Correct 104 ms 14420 KB Output is correct
30 Correct 109 ms 16276 KB Output is correct
31 Correct 100 ms 14396 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 6 ms 7500 KB Output is correct
3 Correct 6 ms 7500 KB Output is correct
4 Correct 3 ms 7244 KB Output is correct
5 Correct 6 ms 7500 KB Output is correct
6 Correct 7 ms 7500 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 3 ms 7372 KB Output is correct
9 Correct 6 ms 7500 KB Output is correct
10 Correct 6 ms 7500 KB Output is correct
11 Correct 6 ms 7492 KB Output is correct
12 Correct 6 ms 7500 KB Output is correct
13 Correct 6 ms 7500 KB Output is correct
14 Correct 6 ms 7500 KB Output is correct
15 Correct 6 ms 7492 KB Output is correct
16 Correct 404 ms 26608 KB Output is correct
17 Correct 854 ms 49524 KB Output is correct
18 Correct 63 ms 11056 KB Output is correct
19 Correct 378 ms 26668 KB Output is correct
20 Correct 863 ms 49896 KB Output is correct
21 Correct 593 ms 35036 KB Output is correct
22 Correct 336 ms 26416 KB Output is correct
23 Correct 871 ms 49572 KB Output is correct
24 Correct 890 ms 49536 KB Output is correct
25 Correct 853 ms 49596 KB Output is correct
26 Correct 361 ms 26460 KB Output is correct
27 Correct 368 ms 26616 KB Output is correct
28 Correct 369 ms 26456 KB Output is correct
29 Correct 375 ms 26764 KB Output is correct
30 Correct 364 ms 26580 KB Output is correct
31 Correct 4 ms 7372 KB Output is correct
32 Correct 3 ms 7372 KB Output is correct
33 Correct 4 ms 7372 KB Output is correct
34 Correct 4 ms 7348 KB Output is correct
35 Correct 4 ms 7344 KB Output is correct
36 Correct 4 ms 7348 KB Output is correct
37 Correct 4 ms 7372 KB Output is correct
38 Correct 5 ms 7372 KB Output is correct
39 Correct 4 ms 7372 KB Output is correct
40 Correct 4 ms 7372 KB Output is correct
41 Correct 259 ms 21532 KB Output is correct
42 Correct 551 ms 38836 KB Output is correct
43 Correct 527 ms 38496 KB Output is correct
44 Correct 106 ms 14460 KB Output is correct
45 Correct 529 ms 38472 KB Output is correct
46 Correct 539 ms 38504 KB Output is correct
47 Correct 535 ms 38624 KB Output is correct
48 Correct 528 ms 38500 KB Output is correct
49 Correct 536 ms 38632 KB Output is correct
50 Correct 528 ms 38504 KB Output is correct
51 Correct 554 ms 38472 KB Output is correct
52 Correct 559 ms 38580 KB Output is correct
53 Correct 545 ms 38568 KB Output is correct
54 Correct 549 ms 38696 KB Output is correct
55 Correct 571 ms 39632 KB Output is correct
56 Correct 553 ms 38524 KB Output is correct
57 Correct 557 ms 38700 KB Output is correct
58 Correct 574 ms 38632 KB Output is correct
59 Correct 99 ms 14452 KB Output is correct
60 Correct 547 ms 38504 KB Output is correct
61 Correct 535 ms 38628 KB Output is correct
62 Correct 110 ms 16264 KB Output is correct
63 Correct 112 ms 14892 KB Output is correct
64 Correct 117 ms 16268 KB Output is correct
65 Correct 108 ms 16236 KB Output is correct
66 Correct 112 ms 15144 KB Output is correct
67 Correct 101 ms 14436 KB Output is correct
68 Correct 108 ms 16232 KB Output is correct
69 Correct 104 ms 14420 KB Output is correct
70 Correct 109 ms 16276 KB Output is correct
71 Correct 100 ms 14396 KB Output is correct
72 Correct 628 ms 37268 KB Output is correct
73 Correct 895 ms 50404 KB Output is correct
74 Correct 877 ms 50348 KB Output is correct
75 Correct 882 ms 50396 KB Output is correct
76 Correct 883 ms 50404 KB Output is correct
77 Correct 918 ms 50412 KB Output is correct
78 Correct 902 ms 50276 KB Output is correct
79 Correct 892 ms 50332 KB Output is correct
80 Correct 917 ms 50372 KB Output is correct
81 Correct 904 ms 50416 KB Output is correct
82 Correct 878 ms 50276 KB Output is correct
83 Correct 870 ms 50344 KB Output is correct
84 Correct 875 ms 50148 KB Output is correct
85 Correct 877 ms 50372 KB Output is correct
86 Correct 876 ms 50292 KB Output is correct
87 Correct 865 ms 50228 KB Output is correct
88 Correct 876 ms 50256 KB Output is correct
89 Correct 420 ms 28660 KB Output is correct
90 Correct 890 ms 50300 KB Output is correct
91 Correct 953 ms 52556 KB Output is correct
92 Correct 404 ms 28896 KB Output is correct
93 Correct 517 ms 55024 KB Output is correct
94 Correct 416 ms 28840 KB Output is correct
95 Correct 414 ms 29028 KB Output is correct
96 Correct 542 ms 57964 KB Output is correct
97 Correct 432 ms 30592 KB Output is correct
98 Correct 430 ms 28820 KB Output is correct
99 Correct 425 ms 30700 KB Output is correct
100 Correct 439 ms 29044 KB Output is correct