Submission #1200861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200861		Braabebo10	Swapping Cities (APIO20_swap)	C++20	37 / 100	2095 ms	27552 KiB

swap

#include "swap.h"
#include<bits/stdc++.h>
#define ll long long
#define nl "\n"
#define all(v) v.begin(),v.end()
#define baraa ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
vector<vector<array<ll, 3> > > adj;
ll n, m;
vector<ll> weights;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N, m = M;
    adj = vector<vector<array<ll, 3> > >(n + 1);
    for (ll i = 0; i < m; i++) {
        adj[U[i]].push_back({V[i], W[i], i});
        adj[V[i]].push_back({U[i], W[i], i});
        weights.push_back(W[i]);
    }
    sort(all(weights));
    weights.erase(unique(all(weights)), weights.end());
}

int getMinimumFuelCapacity(int x, int y) {
    ll l = 0, r = weights.size() - 1, ans = -1;
    while (l <= r) {
        ll mid = (l + r) / 2, ok = 0, ok2 = 0, all = 0, nodes = 0;
        vector<ll> vis(n + 1, 0);
        function<void(ll)> dfs = [&](ll u) {
            if (vis[u])return;
            vis[u] = 1;
            ok |= (u == y);
            ll cnt = 0;
            nodes++;
            for (auto [v, w, idx]: adj[u])
                if (w <= weights[mid])
                    dfs(v), cnt++;
            ok2 |= (cnt >= 3);
            all += cnt;
        };
        dfs(x);
        if (ok and (ok2 or (all / 2) > nodes - 1))ans = weights[mid], 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