Submission #714897

#	Time	Username	Problem	Language	Result	Execution time	Memory
714897		dxz05	Swapping Cities (APIO20_swap)	C++17	37 / 100	2064 ms	14908 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 100005;
vector<tuple<int, int, int>> edges;

int N, M;

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
    N = _N, M = _M;

    for (int i = 0; i < M; i++){
        edges.emplace_back(W[i], U[i], V[i]);
    }

    sort(edges.begin(), edges.end());
}

vector<int> g[MaxN];

vector<bool> used;

void dfs(int v){
    used[v] = true;
    for (int u : g[v]){
        if (!used[u]) dfs(u);
    }
}

bool check(int W, int X, int Y){
    for (int i = 0; i < N; i++) g[i].clear();

    for (auto [w, u, v] : edges){
        if (w <= W){
            g[u].push_back(v);
            g[v].push_back(u);
        }
    }

    used.assign(N, false);
    dfs(X);

    if (!used[Y]) return false;

    int cnt = 0;
    for (int i = 0; i < N; i++){
        if (!used[i]) continue;

        int deg = (int)g[i].size();

        if (deg >= 3) return true;
        if (deg == 1) cnt++;
    }

    return cnt != 2;
}

int getMinimumFuelCapacity(int X, int Y) {
    int ans = -1;
    int l = 0, r = M - 1;
    while (l <= r){
        int mid = (l + r) >> 1;
        int W = get<0>(edges[mid]);

        if (check(W, X, Y)){
            ans = W;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return ans;
}

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