Submission #560272

#	Time	Username	Problem	Language	Result	Execution time	Memory
560272		HappyPacMan	Swapping Cities (APIO20_swap)	C++14	100 / 100	397 ms	43192 KiB

swap

#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 (stderr)

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 / 6
• Subtask 2: 7 / 7
• Subtask 3: 17 / 17
• Subtask 4: 20 / 20
• Subtask 5: 23 / 23
• Subtask 6: 27 / 27