oj.uz

Submission #560272

# Submission time Handle Problem Language Result Execution time Memory
560272 2022-05-11T08:28:47 Z HappyPacMan Swapping Cities (APIO20_swap) C++14
100 / 100
 397 ms 43192 KB 
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 4;
vector<int> sack[maxn];
vector<pair<int,int> > ucond[maxn];
int dsu[maxn],uturn[maxn],adjs[maxn];

void join(int u,int v,int w){
    if(dsu[u] != dsu[v]){
        if(sack[dsu[v]].size() > sack[dsu[u]].size()){
            swap(u,v);
        }
        int temp = dsu[v];
        if(uturn[dsu[u]] == -1 && uturn[temp] != -1){
            uturn[dsu[u]] = w;
        }
        for(int it : sack[temp]){
            sack[dsu[u]].emplace_back(it);
            dsu[it] = dsu[u];
            ucond[it].emplace_back(dsu[it],w);
        }
        sack[temp].clear();
    }else if(uturn[dsu[u]] == -1){
        uturn[dsu[u]] = w;
    }
    adjs[u]++;
    adjs[v]++;
    if((adjs[u] > 2 || adjs[v] > 2) && uturn[dsu[u]] == -1){
        uturn[dsu[u]] = w;
    }
}

void init(int N,int M,vector<int> U,vector<int> V,vector<int> W){
    vector<tuple<int,int,int> > edge;
    for(int i=0;i<N;i++){
        dsu[i] = i;
        uturn[i] = -1;
        sack[i].emplace_back(i);
        ucond[i].emplace_back(i,0);
    }
    for(int i=0;i<M;i++){
        edge.emplace_back(W[i],U[i],V[i]);
    }
    sort(edge.begin(),edge.end());
    for(auto [w,u,v] : edge){
        join(u,v,w);
    }
    for(int i=0;i<N;i++){
        reverse(ucond[i].begin(),ucond[i].end());
    }
}

int getMinimumFuelCapacity(int X,int Y){
    int msize = min(ucond[X].size(),ucond[Y].size()), best = -1;
    for(int i=0;i<msize;i++){
        if(ucond[X][i].first == ucond[Y][i].first && uturn[ucond[X][i].first] != -1){
            if(best == -1){
                best = max({ucond[X][i].second,ucond[Y][i].second,uturn[ucond[X][i].first]});
            }else{
                best = min(best,max({ucond[X][i].second,ucond[Y][i].second,uturn[ucond[X][i].first]}));
            }
        }
    }
    return best;
}

Compilation message

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:46:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     for(auto [w,u,v] : edge){
      |              ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 8 ms 9824 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 23 ms 9888 KB Output is correct
6 Correct 7 ms 9900 KB Output is correct
7 Correct 7 ms 9840 KB Output is correct
8 Correct 7 ms 9840 KB Output is correct
9 Correct 197 ms 28292 KB Output is correct
10 Correct 276 ms 31752 KB Output is correct
11 Correct 273 ms 31400 KB Output is correct
12 Correct 230 ms 32588 KB Output is correct
13 Correct 145 ms 25120 KB Output is correct
14 Correct 201 ms 28320 KB Output is correct
15 Correct 302 ms 35288 KB Output is correct
16 Correct 363 ms 34640 KB Output is correct
17 Correct 397 ms 35944 KB Output is correct
18 Correct 205 ms 28340 KB Output is correct
19 Correct 81 ms 17748 KB Output is correct
20 Correct 378 ms 35648 KB Output is correct
21 Correct 307 ms 35376 KB Output is correct
22 Correct 373 ms 36428 KB Output is correct
23 Correct 229 ms 28828 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 165 ms 25516 KB Output is correct
4 Correct 173 ms 25996 KB Output is correct
5 Correct 175 ms 26164 KB Output is correct
6 Correct 179 ms 25840 KB Output is correct
7 Correct 208 ms 26208 KB Output is correct
8 Correct 181 ms 25684 KB Output is correct
9 Correct 168 ms 26048 KB Output is correct
10 Correct 220 ms 25540 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 8 ms 9824 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 23 ms 9888 KB Output is correct
6 Correct 7 ms 9900 KB Output is correct
7 Correct 7 ms 9840 KB Output is correct
8 Correct 7 ms 9840 KB Output is correct
9 Correct 5 ms 9684 KB Output is correct
10 Correct 38 ms 9848 KB Output is correct
11 Correct 6 ms 9832 KB Output is correct
12 Correct 6 ms 9812 KB Output is correct
13 Correct 73 ms 9828 KB Output is correct
14 Correct 6 ms 9812 KB Output is correct
15 Correct 7 ms 9852 KB Output is correct
16 Correct 6 ms 9812 KB Output is correct
17 Correct 8 ms 9812 KB Output is correct
18 Correct 6 ms 9812 KB Output is correct
19 Correct 7 ms 9772 KB Output is correct
20 Correct 7 ms 9836 KB Output is correct
21 Correct 7 ms 9812 KB Output is correct
22 Correct 7 ms 9812 KB Output is correct
23 Correct 8 ms 9812 KB Output is correct
24 Correct 7 ms 9836 KB Output is correct
25 Correct 7 ms 9900 KB Output is correct
26 Correct 7 ms 9964 KB Output is correct
27 Correct 7 ms 9752 KB Output is correct
28 Correct 7 ms 9884 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 17 ms 9684 KB Output is correct
3 Correct 6 ms 9700 KB Output is correct
4 Correct 8 ms 9824 KB Output is correct
5 Correct 6 ms 9700 KB Output is correct
6 Correct 23 ms 9888 KB Output is correct
7 Correct 7 ms 9900 KB Output is correct
8 Correct 7 ms 9840 KB Output is correct
9 Correct 7 ms 9840 KB Output is correct
10 Correct 197 ms 28292 KB Output is correct
11 Correct 276 ms 31752 KB Output is correct
12 Correct 273 ms 31400 KB Output is correct
13 Correct 230 ms 32588 KB Output is correct
14 Correct 145 ms 25120 KB Output is correct
15 Correct 38 ms 9848 KB Output is correct
16 Correct 6 ms 9832 KB Output is correct
17 Correct 6 ms 9812 KB Output is correct
18 Correct 73 ms 9828 KB Output is correct
19 Correct 6 ms 9812 KB Output is correct
20 Correct 7 ms 9852 KB Output is correct
21 Correct 6 ms 9812 KB Output is correct
22 Correct 8 ms 9812 KB Output is correct
23 Correct 6 ms 9812 KB Output is correct
24 Correct 7 ms 9772 KB Output is correct
25 Correct 7 ms 9836 KB Output is correct
26 Correct 7 ms 9812 KB Output is correct
27 Correct 7 ms 9812 KB Output is correct
28 Correct 8 ms 9812 KB Output is correct
29 Correct 7 ms 9836 KB Output is correct
30 Correct 7 ms 9900 KB Output is correct
31 Correct 7 ms 9964 KB Output is correct
32 Correct 7 ms 9752 KB Output is correct
33 Correct 7 ms 9884 KB Output is correct
34 Correct 19 ms 12440 KB Output is correct
35 Correct 239 ms 33008 KB Output is correct
36 Correct 228 ms 32620 KB Output is correct
37 Correct 225 ms 32108 KB Output is correct
38 Correct 219 ms 31192 KB Output is correct
39 Correct 224 ms 30824 KB Output is correct
40 Correct 148 ms 28764 KB Output is correct
41 Correct 252 ms 33484 KB Output is correct
42 Correct 248 ms 33372 KB Output is correct
43 Correct 160 ms 24688 KB Output is correct
44 Correct 219 ms 30948 KB Output is correct
45 Correct 161 ms 26884 KB Output is correct
46 Correct 239 ms 32464 KB Output is correct
47 Correct 205 ms 29160 KB Output is correct
48 Correct 162 ms 26464 KB Output is correct
49 Correct 71 ms 19484 KB Output is correct
50 Correct 58 ms 16992 KB Output is correct
51 Correct 127 ms 24016 KB Output is correct
52 Correct 322 ms 35416 KB Output is correct
53 Correct 192 ms 31860 KB Output is correct
54 Correct 241 ms 38812 KB Output is correct
55 Correct 130 ms 24848 KB Output is correct
56 Correct 184 ms 30636 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 9684 KB Output is correct
2 Correct 6 ms 9700 KB Output is correct
3 Correct 8 ms 9824 KB Output is correct
4 Correct 6 ms 9700 KB Output is correct
5 Correct 23 ms 9888 KB Output is correct
6 Correct 7 ms 9900 KB Output is correct
7 Correct 7 ms 9840 KB Output is correct
8 Correct 7 ms 9840 KB Output is correct
9 Correct 197 ms 28292 KB Output is correct
10 Correct 276 ms 31752 KB Output is correct
11 Correct 273 ms 31400 KB Output is correct
12 Correct 230 ms 32588 KB Output is correct
13 Correct 145 ms 25120 KB Output is correct
14 Correct 201 ms 28320 KB Output is correct
15 Correct 302 ms 35288 KB Output is correct
16 Correct 363 ms 34640 KB Output is correct
17 Correct 397 ms 35944 KB Output is correct
18 Correct 205 ms 28340 KB Output is correct
19 Correct 165 ms 25516 KB Output is correct
20 Correct 173 ms 25996 KB Output is correct
21 Correct 175 ms 26164 KB Output is correct
22 Correct 179 ms 25840 KB Output is correct
23 Correct 208 ms 26208 KB Output is correct
24 Correct 181 ms 25684 KB Output is correct
25 Correct 168 ms 26048 KB Output is correct
26 Correct 220 ms 25540 KB Output is correct
27 Correct 38 ms 9848 KB Output is correct
28 Correct 6 ms 9832 KB Output is correct
29 Correct 6 ms 9812 KB Output is correct
30 Correct 73 ms 9828 KB Output is correct
31 Correct 6 ms 9812 KB Output is correct
32 Correct 7 ms 9852 KB Output is correct
33 Correct 6 ms 9812 KB Output is correct
34 Correct 8 ms 9812 KB Output is correct
35 Correct 6 ms 9812 KB Output is correct
36 Correct 19 ms 12440 KB Output is correct
37 Correct 239 ms 33008 KB Output is correct
38 Correct 228 ms 32620 KB Output is correct
39 Correct 225 ms 32108 KB Output is correct
40 Correct 219 ms 31192 KB Output is correct
41 Correct 224 ms 30824 KB Output is correct
42 Correct 148 ms 28764 KB Output is correct
43 Correct 252 ms 33484 KB Output is correct
44 Correct 248 ms 33372 KB Output is correct
45 Correct 160 ms 24688 KB Output is correct
46 Correct 219 ms 30948 KB Output is correct
47 Correct 27 ms 12684 KB Output is correct
48 Correct 314 ms 36744 KB Output is correct
49 Correct 308 ms 36192 KB Output is correct
50 Correct 368 ms 36052 KB Output is correct
51 Correct 253 ms 35524 KB Output is correct
52 Correct 259 ms 33696 KB Output is correct
53 Correct 201 ms 28788 KB Output is correct
54 Correct 274 ms 37424 KB Output is correct
55 Correct 302 ms 37464 KB Output is correct
56 Correct 207 ms 29056 KB Output is correct
57 Correct 277 ms 34812 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 17 ms 9684 KB Output is correct
3 Correct 6 ms 9700 KB Output is correct
4 Correct 8 ms 9824 KB Output is correct
5 Correct 6 ms 9700 KB Output is correct
6 Correct 23 ms 9888 KB Output is correct
7 Correct 7 ms 9900 KB Output is correct
8 Correct 7 ms 9840 KB Output is correct
9 Correct 7 ms 9840 KB Output is correct
10 Correct 197 ms 28292 KB Output is correct
11 Correct 276 ms 31752 KB Output is correct
12 Correct 273 ms 31400 KB Output is correct
13 Correct 230 ms 32588 KB Output is correct
14 Correct 145 ms 25120 KB Output is correct
15 Correct 201 ms 28320 KB Output is correct
16 Correct 302 ms 35288 KB Output is correct
17 Correct 363 ms 34640 KB Output is correct
18 Correct 397 ms 35944 KB Output is correct
19 Correct 205 ms 28340 KB Output is correct
20 Correct 165 ms 25516 KB Output is correct
21 Correct 173 ms 25996 KB Output is correct
22 Correct 175 ms 26164 KB Output is correct
23 Correct 179 ms 25840 KB Output is correct
24 Correct 208 ms 26208 KB Output is correct
25 Correct 181 ms 25684 KB Output is correct
26 Correct 168 ms 26048 KB Output is correct
27 Correct 220 ms 25540 KB Output is correct
28 Correct 38 ms 9848 KB Output is correct
29 Correct 6 ms 9832 KB Output is correct
30 Correct 6 ms 9812 KB Output is correct
31 Correct 73 ms 9828 KB Output is correct
32 Correct 6 ms 9812 KB Output is correct
33 Correct 7 ms 9852 KB Output is correct
34 Correct 6 ms 9812 KB Output is correct
35 Correct 8 ms 9812 KB Output is correct
36 Correct 6 ms 9812 KB Output is correct
37 Correct 19 ms 12440 KB Output is correct
38 Correct 239 ms 33008 KB Output is correct
39 Correct 228 ms 32620 KB Output is correct
40 Correct 225 ms 32108 KB Output is correct
41 Correct 219 ms 31192 KB Output is correct
42 Correct 224 ms 30824 KB Output is correct
43 Correct 148 ms 28764 KB Output is correct
44 Correct 252 ms 33484 KB Output is correct
45 Correct 248 ms 33372 KB Output is correct
46 Correct 160 ms 24688 KB Output is correct
47 Correct 219 ms 30948 KB Output is correct
48 Correct 27 ms 12684 KB Output is correct
49 Correct 314 ms 36744 KB Output is correct
50 Correct 308 ms 36192 KB Output is correct
51 Correct 368 ms 36052 KB Output is correct
52 Correct 253 ms 35524 KB Output is correct
53 Correct 259 ms 33696 KB Output is correct
54 Correct 201 ms 28788 KB Output is correct
55 Correct 274 ms 37424 KB Output is correct
56 Correct 302 ms 37464 KB Output is correct
57 Correct 207 ms 29056 KB Output is correct
58 Correct 277 ms 34812 KB Output is correct
59 Correct 81 ms 17748 KB Output is correct
60 Correct 378 ms 35648 KB Output is correct
61 Correct 307 ms 35376 KB Output is correct
62 Correct 373 ms 36428 KB Output is correct
63 Correct 229 ms 28828 KB Output is correct
64 Correct 7 ms 9772 KB Output is correct
65 Correct 7 ms 9836 KB Output is correct
66 Correct 7 ms 9812 KB Output is correct
67 Correct 7 ms 9812 KB Output is correct
68 Correct 8 ms 9812 KB Output is correct
69 Correct 7 ms 9836 KB Output is correct
70 Correct 7 ms 9900 KB Output is correct
71 Correct 7 ms 9964 KB Output is correct
72 Correct 7 ms 9752 KB Output is correct
73 Correct 7 ms 9884 KB Output is correct
74 Correct 161 ms 26884 KB Output is correct
75 Correct 239 ms 32464 KB Output is correct
76 Correct 205 ms 29160 KB Output is correct
77 Correct 162 ms 26464 KB Output is correct
78 Correct 71 ms 19484 KB Output is correct
79 Correct 58 ms 16992 KB Output is correct
80 Correct 127 ms 24016 KB Output is correct
81 Correct 322 ms 35416 KB Output is correct
82 Correct 192 ms 31860 KB Output is correct
83 Correct 241 ms 38812 KB Output is correct
84 Correct 130 ms 24848 KB Output is correct
85 Correct 184 ms 30636 KB Output is correct
86 Correct 89 ms 16928 KB Output is correct
87 Correct 286 ms 35712 KB Output is correct
88 Correct 327 ms 35984 KB Output is correct
89 Correct 197 ms 29520 KB Output is correct
90 Correct 174 ms 23404 KB Output is correct
91 Correct 136 ms 23624 KB Output is correct
92 Correct 184 ms 27612 KB Output is correct
93 Correct 393 ms 38504 KB Output is correct
94 Correct 303 ms 36056 KB Output is correct
95 Correct 390 ms 43192 KB Output is correct
96 Correct 230 ms 28904 KB Output is correct
97 Correct 283 ms 32676 KB Output is correct