oj.uz

Submission #878928

# Submission time Handle Problem Language Result Execution time Memory
878928 2023-11-25T14:38:22 Z TahirAliyev Evacuation plan (IZhO18_plan) C++17
100 / 100
 833 ms 91588 KB 
#include <bits/stdc++.h>
using namespace std;


#define ll long long
#define oo 1e9
#define int ll
#define pii pair<int, int>

int n, m, q, k;
const int MAX = 5e5 + 5;

vector<int> source;
vector<pii> g[MAX];

int dist[MAX];
int par[MAX];
set<int> c[MAX]; 
int ans[MAX];

int find(int node){
    if(par[node] < 0) return node;
    return par[node] = find(par[node]);
}

void unite(int u, int v, int val){
    u = find(u), v = find(v);
    if(u == v) return;
    if(-par[u] < -par[v]) swap(u, v);
    par[u] += par[v];
    par[v] = u;

    if(c[u].size() < c[v].size()) swap(c[u], c[v]);
    for(int a : c[v]){
        if(c[u].find(a) != c[u].end()){
            ans[a] = max(val, ans[a]);
            c[u].erase(a);
        }
        else{
            c[u].insert(a);
        }
    }
}

void djikstra(){
    for(int i = 1; i <= n; i++){
        dist[i] = oo;
    }
    set<pii> s;
    for(int a : source){
        dist[a] = 0;
        s.insert({0, a});
    }
    while(s.size()){
        int node = s.begin() -> second;
        s.erase(s.begin());
        for(pii to : g[node]){
            if(dist[to.first] > dist[node] + to.second){
                s.erase({dist[to.first], to.first});
                dist[to.first] = dist[node] + to.second;
                s.insert({dist[to.first], to.first});
            }
        }
    }
}

bool open[MAX];

signed main(){
    memset(par, -1, sizeof(par));
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int a, b, d; cin >> a >> b >> d;
        g[a].push_back({b, d});
        g[b].push_back({a, d});
    }
    cin >> k;
    for(int i = 1; i <= k; i++){
        int a; cin >> a;
        source.push_back(a);
    }
    djikstra();
    cin >> q;
    for(int i = 1; i <= q; i++){
        int a, b; cin >> a >> b;
        c[a].insert(i);
        c[b].insert(i);
    }
    vector<pii> v;
    for(int i = 1; i <= n; i++){
        v.push_back({dist[i], i});
    }
    sort(v.rbegin(), v.rend());
    for(auto node : v){
        for(pii to : g[node.second]){
            if(open[to.first]){
                unite(node.second, to.first, node.first);
            }
        }
        open[node.second] = 1;
    }
    for(int i = 1; i <= q; i++){
        cout << ans[i] << '\n';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 41564 KB Output is correct
2 Correct 10 ms 41564 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 8 ms 41560 KB Output is correct
5 Correct 11 ms 41792 KB Output is correct
6 Correct 11 ms 41564 KB Output is correct
7 Correct 9 ms 41544 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 9 ms 41776 KB Output is correct
10 Correct 10 ms 41624 KB Output is correct
11 Correct 10 ms 41584 KB Output is correct
12 Correct 10 ms 41564 KB Output is correct
13 Correct 10 ms 41784 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 41564 KB Output is correct
2 Correct 10 ms 41564 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 8 ms 41560 KB Output is correct
5 Correct 11 ms 41792 KB Output is correct
6 Correct 11 ms 41564 KB Output is correct
7 Correct 9 ms 41544 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 9 ms 41776 KB Output is correct
10 Correct 10 ms 41624 KB Output is correct
11 Correct 10 ms 41584 KB Output is correct
12 Correct 10 ms 41564 KB Output is correct
13 Correct 10 ms 41784 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct
16 Correct 276 ms 62224 KB Output is correct
17 Correct 807 ms 89040 KB Output is correct
18 Correct 60 ms 46032 KB Output is correct
19 Correct 247 ms 61384 KB Output is correct
20 Correct 743 ms 89388 KB Output is correct
21 Correct 411 ms 71936 KB Output is correct
22 Correct 210 ms 61888 KB Output is correct
23 Correct 762 ms 89024 KB Output is correct
24 Correct 775 ms 89252 KB Output is correct
25 Correct 833 ms 89356 KB Output is correct
26 Correct 248 ms 61632 KB Output is correct
27 Correct 255 ms 61636 KB Output is correct
28 Correct 241 ms 61456 KB Output is correct
29 Correct 245 ms 61536 KB Output is correct
30 Correct 249 ms 61656 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 41564 KB Output is correct
2 Correct 9 ms 41564 KB Output is correct
3 Correct 8 ms 41564 KB Output is correct
4 Correct 9 ms 41564 KB Output is correct
5 Correct 8 ms 41564 KB Output is correct
6 Correct 8 ms 41564 KB Output is correct
7 Correct 8 ms 41512 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 8 ms 41564 KB Output is correct
10 Correct 9 ms 41560 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 56400 KB Output is correct
2 Correct 602 ms 78836 KB Output is correct
3 Correct 539 ms 79700 KB Output is correct
4 Correct 94 ms 50020 KB Output is correct
5 Correct 576 ms 79424 KB Output is correct
6 Correct 623 ms 78964 KB Output is correct
7 Correct 577 ms 79204 KB Output is correct
8 Correct 542 ms 78000 KB Output is correct
9 Correct 536 ms 79444 KB Output is correct
10 Correct 514 ms 79116 KB Output is correct
11 Correct 562 ms 79344 KB Output is correct
12 Correct 529 ms 79536 KB Output is correct
13 Correct 515 ms 79300 KB Output is correct
14 Correct 552 ms 78924 KB Output is correct
15 Correct 569 ms 79644 KB Output is correct
16 Correct 530 ms 78828 KB Output is correct
17 Correct 538 ms 79492 KB Output is correct
18 Correct 545 ms 79444 KB Output is correct
19 Correct 97 ms 49868 KB Output is correct
20 Correct 531 ms 79600 KB Output is correct
21 Correct 505 ms 80284 KB Output is correct
22 Correct 122 ms 55596 KB Output is correct
23 Correct 105 ms 50408 KB Output is correct
24 Correct 126 ms 55696 KB Output is correct
25 Correct 129 ms 54208 KB Output is correct
26 Correct 114 ms 50760 KB Output is correct
27 Correct 94 ms 50076 KB Output is correct
28 Correct 126 ms 55744 KB Output is correct
29 Correct 101 ms 49868 KB Output is correct
30 Correct 130 ms 55776 KB Output is correct
31 Correct 96 ms 49928 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 41564 KB Output is correct
2 Correct 10 ms 41564 KB Output is correct
3 Correct 10 ms 41564 KB Output is correct
4 Correct 8 ms 41560 KB Output is correct
5 Correct 11 ms 41792 KB Output is correct
6 Correct 11 ms 41564 KB Output is correct
7 Correct 9 ms 41544 KB Output is correct
8 Correct 8 ms 41564 KB Output is correct
9 Correct 9 ms 41776 KB Output is correct
10 Correct 10 ms 41624 KB Output is correct
11 Correct 10 ms 41584 KB Output is correct
12 Correct 10 ms 41564 KB Output is correct
13 Correct 10 ms 41784 KB Output is correct
14 Correct 10 ms 41564 KB Output is correct
15 Correct 10 ms 41564 KB Output is correct
16 Correct 276 ms 62224 KB Output is correct
17 Correct 807 ms 89040 KB Output is correct
18 Correct 60 ms 46032 KB Output is correct
19 Correct 247 ms 61384 KB Output is correct
20 Correct 743 ms 89388 KB Output is correct
21 Correct 411 ms 71936 KB Output is correct
22 Correct 210 ms 61888 KB Output is correct
23 Correct 762 ms 89024 KB Output is correct
24 Correct 775 ms 89252 KB Output is correct
25 Correct 833 ms 89356 KB Output is correct
26 Correct 248 ms 61632 KB Output is correct
27 Correct 255 ms 61636 KB Output is correct
28 Correct 241 ms 61456 KB Output is correct
29 Correct 245 ms 61536 KB Output is correct
30 Correct 249 ms 61656 KB Output is correct
31 Correct 8 ms 41564 KB Output is correct
32 Correct 9 ms 41564 KB Output is correct
33 Correct 8 ms 41564 KB Output is correct
34 Correct 9 ms 41564 KB Output is correct
35 Correct 8 ms 41564 KB Output is correct
36 Correct 8 ms 41564 KB Output is correct
37 Correct 8 ms 41512 KB Output is correct
38 Correct 8 ms 41564 KB Output is correct
39 Correct 8 ms 41564 KB Output is correct
40 Correct 9 ms 41560 KB Output is correct
41 Correct 253 ms 56400 KB Output is correct
42 Correct 602 ms 78836 KB Output is correct
43 Correct 539 ms 79700 KB Output is correct
44 Correct 94 ms 50020 KB Output is correct
45 Correct 576 ms 79424 KB Output is correct
46 Correct 623 ms 78964 KB Output is correct
47 Correct 577 ms 79204 KB Output is correct
48 Correct 542 ms 78000 KB Output is correct
49 Correct 536 ms 79444 KB Output is correct
50 Correct 514 ms 79116 KB Output is correct
51 Correct 562 ms 79344 KB Output is correct
52 Correct 529 ms 79536 KB Output is correct
53 Correct 515 ms 79300 KB Output is correct
54 Correct 552 ms 78924 KB Output is correct
55 Correct 569 ms 79644 KB Output is correct
56 Correct 530 ms 78828 KB Output is correct
57 Correct 538 ms 79492 KB Output is correct
58 Correct 545 ms 79444 KB Output is correct
59 Correct 97 ms 49868 KB Output is correct
60 Correct 531 ms 79600 KB Output is correct
61 Correct 505 ms 80284 KB Output is correct
62 Correct 122 ms 55596 KB Output is correct
63 Correct 105 ms 50408 KB Output is correct
64 Correct 126 ms 55696 KB Output is correct
65 Correct 129 ms 54208 KB Output is correct
66 Correct 114 ms 50760 KB Output is correct
67 Correct 94 ms 50076 KB Output is correct
68 Correct 126 ms 55744 KB Output is correct
69 Correct 101 ms 49868 KB Output is correct
70 Correct 130 ms 55776 KB Output is correct
71 Correct 96 ms 49928 KB Output is correct
72 Correct 458 ms 73916 KB Output is correct
73 Correct 726 ms 90028 KB Output is correct
74 Correct 750 ms 90196 KB Output is correct
75 Correct 729 ms 90184 KB Output is correct
76 Correct 728 ms 90076 KB Output is correct
77 Correct 708 ms 90052 KB Output is correct
78 Correct 771 ms 90008 KB Output is correct
79 Correct 700 ms 89976 KB Output is correct
80 Correct 705 ms 90304 KB Output is correct
81 Correct 763 ms 90056 KB Output is correct
82 Correct 715 ms 90260 KB Output is correct
83 Correct 717 ms 90148 KB Output is correct
84 Correct 730 ms 90148 KB Output is correct
85 Correct 699 ms 90052 KB Output is correct
86 Correct 689 ms 90048 KB Output is correct
87 Correct 712 ms 89808 KB Output is correct
88 Correct 710 ms 89920 KB Output is correct
89 Correct 256 ms 64028 KB Output is correct
90 Correct 678 ms 89844 KB Output is correct
91 Correct 672 ms 90952 KB Output is correct
92 Correct 285 ms 63552 KB Output is correct
93 Correct 340 ms 87908 KB Output is correct
94 Correct 282 ms 63808 KB Output is correct
95 Correct 274 ms 63620 KB Output is correct
96 Correct 382 ms 91588 KB Output is correct
97 Correct 262 ms 66116 KB Output is correct
98 Correct 270 ms 63452 KB Output is correct
99 Correct 272 ms 66436 KB Output is correct
100 Correct 269 ms 63520 KB Output is correct