oj.uz

Submission #560267

# Submission time Handle Problem Language Result Execution time Memory
560267 2022-05-11T08:25:48 Z HappyPacMan Swapping Cities (APIO20_swap) C++14
13 / 100
 283 ms 33684 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[u] == -1 && uturn[temp] != -1){
            uturn[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 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9832 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 122 ms 26728 KB Output is correct
10 Correct 193 ms 30276 KB Output is correct
11 Correct 151 ms 29872 KB Output is correct
12 Correct 170 ms 31060 KB Output is correct
13 Correct 118 ms 23616 KB Output is correct
14 Correct 149 ms 26716 KB Output is correct
15 Correct 226 ms 32208 KB Output is correct
16 Correct 283 ms 31584 KB Output is correct
17 Correct 231 ms 32916 KB Output is correct
18 Correct 189 ms 25136 KB Output is correct
19 Correct 69 ms 16140 KB Output is correct
20 Correct 248 ms 33024 KB Output is correct
21 Correct 239 ms 32440 KB Output is correct
22 Correct 271 ms 33684 KB Output is correct
23 Correct 172 ms 26184 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 141 ms 23000 KB Output is correct
4 Correct 153 ms 23180 KB Output is correct
5 Correct 190 ms 23144 KB Output is correct
6 Correct 160 ms 23128 KB Output is correct
7 Correct 171 ms 23240 KB Output is correct
8 Correct 166 ms 22764 KB Output is correct
9 Correct 147 ms 23044 KB Output is correct
10 Correct 162 ms 22768 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9832 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 7 ms 9676 KB Output is correct
10 Correct 6 ms 9812 KB Output is correct
11 Incorrect 5 ms 9812 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9832 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 122 ms 26728 KB Output is correct
11 Correct 193 ms 30276 KB Output is correct
12 Correct 151 ms 29872 KB Output is correct
13 Correct 170 ms 31060 KB Output is correct
14 Correct 118 ms 23616 KB Output is correct
15 Correct 6 ms 9812 KB Output is correct
16 Incorrect 5 ms 9812 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9684 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 6 ms 9812 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9832 KB Output is correct
8 Correct 6 ms 9812 KB Output is correct
9 Correct 122 ms 26728 KB Output is correct
10 Correct 193 ms 30276 KB Output is correct
11 Correct 151 ms 29872 KB Output is correct
12 Correct 170 ms 31060 KB Output is correct
13 Correct 118 ms 23616 KB Output is correct
14 Correct 149 ms 26716 KB Output is correct
15 Correct 226 ms 32208 KB Output is correct
16 Correct 283 ms 31584 KB Output is correct
17 Correct 231 ms 32916 KB Output is correct
18 Correct 189 ms 25136 KB Output is correct
19 Correct 141 ms 23000 KB Output is correct
20 Correct 153 ms 23180 KB Output is correct
21 Correct 190 ms 23144 KB Output is correct
22 Correct 160 ms 23128 KB Output is correct
23 Correct 171 ms 23240 KB Output is correct
24 Correct 166 ms 22764 KB Output is correct
25 Correct 147 ms 23044 KB Output is correct
26 Correct 162 ms 22768 KB Output is correct
27 Correct 6 ms 9812 KB Output is correct
28 Incorrect 5 ms 9812 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Correct 5 ms 9684 KB Output is correct
3 Correct 5 ms 9684 KB Output is correct
4 Correct 5 ms 9684 KB Output is correct
5 Correct 5 ms 9684 KB Output is correct
6 Correct 6 ms 9812 KB Output is correct
7 Correct 6 ms 9812 KB Output is correct
8 Correct 6 ms 9832 KB Output is correct
9 Correct 6 ms 9812 KB Output is correct
10 Correct 122 ms 26728 KB Output is correct
11 Correct 193 ms 30276 KB Output is correct
12 Correct 151 ms 29872 KB Output is correct
13 Correct 170 ms 31060 KB Output is correct
14 Correct 118 ms 23616 KB Output is correct
15 Correct 149 ms 26716 KB Output is correct
16 Correct 226 ms 32208 KB Output is correct
17 Correct 283 ms 31584 KB Output is correct
18 Correct 231 ms 32916 KB Output is correct
19 Correct 189 ms 25136 KB Output is correct
20 Correct 141 ms 23000 KB Output is correct
21 Correct 153 ms 23180 KB Output is correct
22 Correct 190 ms 23144 KB Output is correct
23 Correct 160 ms 23128 KB Output is correct
24 Correct 171 ms 23240 KB Output is correct
25 Correct 166 ms 22764 KB Output is correct
26 Correct 147 ms 23044 KB Output is correct
27 Correct 162 ms 22768 KB Output is correct
28 Correct 6 ms 9812 KB Output is correct
29 Incorrect 5 ms 9812 KB Output isn't correct
30 Halted 0 ms 0 KB -