Submission #1189294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189294		zh_h	Swapping Cities (APIO20_swap)	C++17	7 / 100	52 ms	6108 KiB

swap

#include <bits/stdc++.h>
#define pb push_back
#define lint long long int
using namespace std;

pair<int, int> min1={1e9, -1}, min2={1e9, -1}, min3={1e9, -1};
vector<int> edge;

void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) {
    edge.resize(n);
    for (int i = 0; i < m; i ++) {
        edge[V[i]] = W[i];
    }
    
    for (int i = 0; i < m; i ++) {
        if (W[i] <= min1.first) {
            min3 = min2;
            min2 = min1;
            min1 = {W[i], V[i]};
        }
        else if (W[i] <= min2.first) {
            min3 = min2;
            min2 = {W[i], V[i]};
        }
        else if (W[i] <= min3.first) {
            min3 = {W[i], V[i]};
        }
    }
}

int getMinimumFuelCapacity(int x, int y) {
    if (edge.size() <= 3) {
        return -1;
    }
    else if (x == 0 || y == 0) {
        if (x > y) {swap(x, y);}
        int road1, road2;
        if (y == min1.second) {
            road1 = min2.first; road2 = min3.first;
        }
        else if (y == min2.second) {
            road1 = min1.first; road2 = min3.first;
        }
        else {
            road1 = min1.first, road2 = min2.first;
        }
        return max({road1, road2, edge[y]});
    }
    else {
        if (x != min1.second && y != min1.second) {
            return max({min1.first, edge[x], edge[y]});
        }
        else if (x != min2.second && y != min2.second) {
            return max({min2.first, edge[x], edge[y]});
        }
        else {
            return max({min3.first, edge[x], edge[y]});
        }
    }
}

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