Submission #304145

#	Time	Username	Problem	Language	Result	Execution time	Memory
304145		kkm0476	Swapping Cities (APIO20_swap)	C++17	6 / 100	2074 ms	22884 KiB

swap

#include "swap.h"
#include <vector>
#include <utility>
#include <iostream>
#include <algorithm>

std::vector<int> r[100010];
std::vector<std::pair<int, int> > w, w1;

int mx_ = 0;
int subt = 1;

bool cmp(std::pair<int, int> a, std::pair<int, int> b) {
    return a.first < b.first;
}


void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    std::vector<int> next[N + 1];
    for(int i = 0; i < M; i++) {
        r[U[i]].push_back(i);
        r[V[i]].push_back(i);
        next[U[i]].push_back(V[i]);
        next[V[i]].push_back(U[i]);
        mx_ = std::max(mx_, W[i]);
        w.push_back({W[i], i});
        w1.push_back({W[i], i});
    }
    
    for(int i = 0; i < N; i++)
        if(next[i].size() != 2)
            mx_ = -1;
    if(N > 3 && M == N - 1 && next[0].size() == M)
        subt = 2;
    sort(w.begin(), w.end(), cmp);
}

int getMinimumFuelCapacity(int X, int Y) {
    if(subt == 1)
        return mx_;
    std::vector<std::pair<int, int> > W = w;
    std::vector<std::pair<int, int> > W1 = w1;
    if(X > Y)
        std::swap(X, Y);

    int a = W1[r[X].back()].first;
    int b = W1[r[Y].back()].first;
    
    std::pair<int, int> x = W1[r[X].back()];
    std::pair<int, int> y = W1[r[Y].back()];
    
    if(X == 0) {
        a = b;
        x = y;
    }

    int mx = std::max(a, b);
    
    
    if(std::lower_bound(W.begin(), W.end(), x) != W.end())
        W.erase(std::lower_bound(W.begin(), W.end(), x));
    if(X != 0 && std::lower_bound(W.begin(), W.end(), y) != W.end())
        W.erase(std::lower_bound(W.begin(), W.end(), y));
    
    return std::max(mx, W[0].first);
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:33:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     if(N > 3 && M == N - 1 && next[0].size() == M)
      |                               ~~~~~~~~~~~~~~~^~~~

• Subtask 1: 6 / 6
• Subtask 2: 0 / 7
• Subtask 3: 0 / 17
• Subtask 4: 0 / 20
• Subtask 5: 0 / 23
• Subtask 6: 0 / 27