Submission #397839

#	Time	Username	Problem	Language	Result	Execution time	Memory
397839		yuto1115	Swapping Cities (APIO20_swap)	C++17	50 / 100	2082 ms	17856 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const int inf = 1001001001;

class unionfind {
    int n;
    vi par, rank;
public:
    unionfind(int n) : n(n), par(n, -1), rank(n, 0) {}
    
    int root(int x) {
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }
    
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x), y = root(y);
        if (x == y) return false;
        if (rank[x] < rank[y]) swap(x, y);
        if (rank[x] == rank[y]) rank[x]++;
        par[x] += par[y];
        par[y] = x;
        return true;
    }
};

namespace {
    int n;
    int m;
    vvp G;
    vi deg;
    int mx_w;
    int mx_deg;
    bool cycle;
}

void init(int _n, int _m, vi u, vi v, vi w) {
    n = _n;
    m = _m;
    G.resize(n);
    deg.resize(n);
    mx_w = 0;
    rep(i, m) {
        G[u[i]].eb(v[i], w[i]);
        G[v[i]].eb(u[i], w[i]);
        deg[u[i]]++;
        deg[v[i]]++;
        chmax(mx_w, w[i]);
    }
    cycle = all_of(all(deg), [](int i) { return i == 2; });
    mx_deg = *max_element(all(deg));
    sort(all(G[0]), [](P a, P b) { return a.second < b.second; });
}

// subtask 2
int getMinimumFuelCapacity(int x, int y) {
    // subtask 1
    if (mx_deg <= 2) {
        return (cycle ? mx_w : -1);
    }
    // subtask 2
    if (m <= n - 1 and deg[0] == m) {
        if (n <= 3) return -1;
        if (x == 0) {
            int ans = G[y][0].second;
            int cnt = 0;
            for (auto[v, w] : G[0]) {
                if (v == y) continue;
                chmax(ans, w);
                cnt++;
                if (cnt == 2) break;
            }
            return ans;
        } else {
            int ans = max(G[x][0].second, G[y][0].second);
            for (auto[v, w] : G[0]) {
                if (v == x or v == y) continue;
                chmax(ans, w);
                break;
            }
            return ans;
        }
    }
    // subtask 3,4
    {
        int ok = inf, ng = 0;
        auto f = [&](int l) -> bool {
            unionfind uf(n);
            vi d(n);
            rep(i, n) for (auto[j, w] : G[i]) {
                    if (i > j) continue;
                    if (w > l) continue;
                    uf.merge(i, j);
                    d[i]++;
                    d[j]++;
                }
            if (!uf.same(x, y)) return false;
            bool res = true;
            rep(i, n) {
                if (!uf.same(i, x)) continue;
                if (d[i] > 2) return true;
                if (d[i] == 1) res = false;
            }
            return res;
        };
        if (!f(ok)) return -1;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            (f(mid) ? ok : ng) = mid;
        }
        return ok;
    }
}

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