oj.uz

Submission #767631

# Submission time Handle Problem Language Result Execution time Memory
767631 2023-06-27T00:12:04 Z Trunkty Evacuation plan (IZhO18_plan) C++14
100 / 100
 1114 ms 103620 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll

int n,m,k,q,curr;
vector<vector<int>> roads[100005];
int best[100005];
bool check[100005];
int ans[100005];

//

int root[100005];
set<int> vals[100005];

int findroot(int x){
    if(root[x]!=x){
        root[x] = findroot(root[x]);
    }
    return root[x];
}

void domerge(int x, int y){
    x = findroot(x);
    y = findroot(y);
    if(x==y){
        return;
    }
    if(vals[x].size()>vals[y].size()){
        swap(x,y);
    }
    for(int i:vals[x]){
        if(vals[y].find(i)!=vals[y].end()){
            ans[i] = curr;
            vals[y].erase(i);
        }
        else{
            vals[y].insert(i);
        }
    }
    vals[x].clear();
    root[x] = y;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        best[i] = 2e9;
        root[i] = i;
    }
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin >> a >> b >> c;
        roads[a].push_back({b,c});
        roads[b].push_back({a,c});
    }
    priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;
    cin >> k;
    for(int i=1;i<=k;i++){
        int a;
        cin >> a;
        best[a] = 0;
        pq.push({0,a});
    }
    while(pq.size()>0){
        while(pq.size()>0 and check[pq.top()[1]]){
            pq.pop();
        }
        if(pq.size()==0){
            break;
        }
        int x = pq.top()[1];
        check[x] = true;
        pq.pop();
        for(vector<int> i:roads[x]){
            if(best[i[0]]>best[x]+i[1]){
                best[i[0]] = best[x]+i[1];
                pq.push({best[i[0]],i[0]});
            }
        }
    }
    vector<vector<int>> ord;
    for(int i=1;i<=n;i++){
        ord.push_back({best[i],i});
    }
    sort(ord.begin(),ord.end(),greater<vector<int>>());
    cin >> q;
    for(int i=1;i<=q;i++){
        int a,b;
        cin >> a >> b;
        vals[a].insert(i);
        vals[b].insert(i);
    }
    for(vector<int> i:ord){
        curr = i[0];
        for(vector<int> j:roads[i[1]]){
            if(best[j[0]]>=curr){
                domerge(i[1],j[0]);
            }
        }
    }
    for(int i=1;i<=q;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7652 KB Output is correct
3 Correct 5 ms 7644 KB Output is correct
4 Correct 3 ms 7372 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 4 ms 7648 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 5 ms 7644 KB Output is correct
11 Correct 5 ms 7636 KB Output is correct
12 Correct 5 ms 7648 KB Output is correct
13 Correct 5 ms 7644 KB Output is correct
14 Correct 4 ms 7636 KB Output is correct
15 Correct 4 ms 7644 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7652 KB Output is correct
3 Correct 5 ms 7644 KB Output is correct
4 Correct 3 ms 7372 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 4 ms 7648 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 5 ms 7644 KB Output is correct
11 Correct 5 ms 7636 KB Output is correct
12 Correct 5 ms 7648 KB Output is correct
13 Correct 5 ms 7644 KB Output is correct
14 Correct 4 ms 7636 KB Output is correct
15 Correct 4 ms 7644 KB Output is correct
16 Correct 286 ms 39764 KB Output is correct
17 Correct 1068 ms 103452 KB Output is correct
18 Correct 42 ms 15680 KB Output is correct
19 Correct 263 ms 42160 KB Output is correct
20 Correct 1066 ms 103476 KB Output is correct
21 Correct 446 ms 57164 KB Output is correct
22 Correct 158 ms 40976 KB Output is correct
23 Correct 1077 ms 103364 KB Output is correct
24 Correct 1106 ms 103468 KB Output is correct
25 Correct 950 ms 103620 KB Output is correct
26 Correct 251 ms 41904 KB Output is correct
27 Correct 247 ms 41992 KB Output is correct
28 Correct 242 ms 41848 KB Output is correct
29 Correct 253 ms 41952 KB Output is correct
30 Correct 258 ms 42044 KB Output is correct

Subtask #3
12.0 / 12.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 45372 KB Output is correct
2 Correct 740 ms 94552 KB Output is correct
3 Correct 811 ms 95156 KB Output is correct
4 Correct 109 ms 28560 KB Output is correct
5 Correct 865 ms 95112 KB Output is correct
6 Correct 895 ms 94844 KB Output is correct
7 Correct 961 ms 95168 KB Output is correct
8 Correct 889 ms 94940 KB Output is correct
9 Correct 880 ms 95052 KB Output is correct
10 Correct 940 ms 95124 KB Output is correct
11 Correct 774 ms 95100 KB Output is correct
12 Correct 847 ms 94692 KB Output is correct
13 Correct 865 ms 94944 KB Output is correct
14 Correct 896 ms 94860 KB Output is correct
15 Correct 880 ms 95104 KB Output is correct
16 Correct 868 ms 95172 KB Output is correct
17 Correct 765 ms 94952 KB Output is correct
18 Correct 875 ms 95044 KB Output is correct
19 Correct 98 ms 28616 KB Output is correct
20 Correct 849 ms 95080 KB Output is correct
21 Correct 813 ms 93204 KB Output is correct
22 Correct 152 ms 32976 KB Output is correct
23 Correct 153 ms 28920 KB Output is correct
24 Correct 162 ms 32960 KB Output is correct
25 Correct 154 ms 32808 KB Output is correct
26 Correct 161 ms 29076 KB Output is correct
27 Correct 113 ms 28612 KB Output is correct
28 Correct 148 ms 32820 KB Output is correct
29 Correct 101 ms 28668 KB Output is correct
30 Correct 152 ms 32988 KB Output is correct
31 Correct 104 ms 28608 KB Output is correct

Subtask #5
46.0 / 46.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7380 KB Output is correct
2 Correct 4 ms 7652 KB Output is correct
3 Correct 5 ms 7644 KB Output is correct
4 Correct 3 ms 7372 KB Output is correct
5 Correct 5 ms 7636 KB Output is correct
6 Correct 4 ms 7648 KB Output is correct
7 Correct 3 ms 7380 KB Output is correct
8 Correct 4 ms 7380 KB Output is correct
9 Correct 4 ms 7636 KB Output is correct
10 Correct 5 ms 7644 KB Output is correct
11 Correct 5 ms 7636 KB Output is correct
12 Correct 5 ms 7648 KB Output is correct
13 Correct 5 ms 7644 KB Output is correct
14 Correct 4 ms 7636 KB Output is correct
15 Correct 4 ms 7644 KB Output is correct
16 Correct 286 ms 39764 KB Output is correct
17 Correct 1068 ms 103452 KB Output is correct
18 Correct 42 ms 15680 KB Output is correct
19 Correct 263 ms 42160 KB Output is correct
20 Correct 1066 ms 103476 KB Output is correct
21 Correct 446 ms 57164 KB Output is correct
22 Correct 158 ms 40976 KB Output is correct
23 Correct 1077 ms 103364 KB Output is correct
24 Correct 1106 ms 103468 KB Output is correct
25 Correct 950 ms 103620 KB Output is correct
26 Correct 251 ms 41904 KB Output is correct
27 Correct 247 ms 41992 KB Output is correct
28 Correct 242 ms 41848 KB Output is correct
29 Correct 253 ms 41952 KB Output is correct
30 Correct 258 ms 42044 KB Output is correct
31 Correct 3 ms 7380 KB Output is correct
32 Correct 4 ms 7380 KB Output is correct
33 Correct 3 ms 7380 KB Output is correct
34 Correct 4 ms 7380 KB Output is correct
35 Correct 3 ms 7380 KB Output is correct
36 Correct 3 ms 7380 KB Output is correct
37 Correct 3 ms 7380 KB Output is correct
38 Correct 3 ms 7380 KB Output is correct
39 Correct 4 ms 7380 KB Output is correct
40 Correct 4 ms 7380 KB Output is correct
41 Correct 335 ms 45372 KB Output is correct
42 Correct 740 ms 94552 KB Output is correct
43 Correct 811 ms 95156 KB Output is correct
44 Correct 109 ms 28560 KB Output is correct
45 Correct 865 ms 95112 KB Output is correct
46 Correct 895 ms 94844 KB Output is correct
47 Correct 961 ms 95168 KB Output is correct
48 Correct 889 ms 94940 KB Output is correct
49 Correct 880 ms 95052 KB Output is correct
50 Correct 940 ms 95124 KB Output is correct
51 Correct 774 ms 95100 KB Output is correct
52 Correct 847 ms 94692 KB Output is correct
53 Correct 865 ms 94944 KB Output is correct
54 Correct 896 ms 94860 KB Output is correct
55 Correct 880 ms 95104 KB Output is correct
56 Correct 868 ms 95172 KB Output is correct
57 Correct 765 ms 94952 KB Output is correct
58 Correct 875 ms 95044 KB Output is correct
59 Correct 98 ms 28616 KB Output is correct
60 Correct 849 ms 95080 KB Output is correct
61 Correct 813 ms 93204 KB Output is correct
62 Correct 152 ms 32976 KB Output is correct
63 Correct 153 ms 28920 KB Output is correct
64 Correct 162 ms 32960 KB Output is correct
65 Correct 154 ms 32808 KB Output is correct
66 Correct 161 ms 29076 KB Output is correct
67 Correct 113 ms 28612 KB Output is correct
68 Correct 148 ms 32820 KB Output is correct
69 Correct 101 ms 28668 KB Output is correct
70 Correct 152 ms 32988 KB Output is correct
71 Correct 104 ms 28608 KB Output is correct
72 Correct 484 ms 56936 KB Output is correct
73 Correct 1012 ms 103536 KB Output is correct
74 Correct 1014 ms 103620 KB Output is correct
75 Correct 1046 ms 103536 KB Output is correct
76 Correct 1014 ms 103492 KB Output is correct
77 Correct 995 ms 103608 KB Output is correct
78 Correct 1018 ms 103588 KB Output is correct
79 Correct 1066 ms 103504 KB Output is correct
80 Correct 1012 ms 103544 KB Output is correct
81 Correct 1036 ms 103444 KB Output is correct
82 Correct 1012 ms 103428 KB Output is correct
83 Correct 1010 ms 103556 KB Output is correct
84 Correct 907 ms 103456 KB Output is correct
85 Correct 1114 ms 103560 KB Output is correct
86 Correct 922 ms 103528 KB Output is correct
87 Correct 1029 ms 103492 KB Output is correct
88 Correct 1061 ms 103512 KB Output is correct
89 Correct 258 ms 40872 KB Output is correct
90 Correct 1076 ms 103492 KB Output is correct
91 Correct 1000 ms 102900 KB Output is correct
92 Correct 277 ms 41848 KB Output is correct
93 Correct 403 ms 41344 KB Output is correct
94 Correct 278 ms 41796 KB Output is correct
95 Correct 295 ms 41968 KB Output is correct
96 Correct 371 ms 40744 KB Output is correct
97 Correct 256 ms 40596 KB Output is correct
98 Correct 319 ms 41788 KB Output is correct
99 Correct 257 ms 40604 KB Output is correct
100 Correct 297 ms 42024 KB Output is correct