Submission #1168139

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168139		wii	Swapping Cities (APIO20_swap)	C++20	100 / 100	176 ms	23580 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

const int MaxN = 4e5 + 5;
const int LOG = __lg(MaxN);

#define all(x) (x).begin(), (x).end()
#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)

template<typename T> bool maximize(T &res, const T &val) { if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) { if (val < res) { res = val; return true; } return false; }

const int Inf = 1e9 + 1e8;

int id[MaxN];
vector<int> w;

namespace Dsu {
    int f[MaxN];
    int size[MaxN];
    int cache_time = -1;
    int time_changed[MaxN];
    int cycle_time[MaxN];

    int deg[MaxN];
    vector<pair<int, int>> max_deg[MaxN];

    void init(int n) {
        cache_time = -1;
        for (int i = 0; i < n; ++i) {
            time_changed[i] = -1;
            cycle_time[i] = Inf;
            size[i] = 1;
            f[i] = i;
            deg[i] = 0;
            max_deg[i].push_back({-1, 0});
        }
    }

    int fset(int u, int time) {
        if (u == f[u] || time_changed[u] > time)
            return u;

        return fset(f[u], time);
    }

    void uset(int u, int v, int time = ++cache_time) {
        int U = u, V = v;

        u = fset(u, time);
        v = fset(v, time);

        if (u != v) {
            if (size[u] < size[v])
                swap(u, v);

            f[v] = u;
            size[u] += size[v];
            time_changed[v] = time;
            // minimize(cycle_time[u], cycle_time[v]);
        } else {
            minimize(cycle_time[u], time);
        }

        ++deg[U]; ++deg[V];
        int best = max({deg[U], deg[V], max_deg[v].back().second});

        if (best > max_deg[u].back().second)
            max_deg[u].push_back({time, best});
    }

    int cycled(int u, int time) {
        return cycle_time[u] <= time;
    }
}

using namespace Dsu;

int n, m;
void init(int N, int M, std::vector<int> u, std::vector<int> v, std::vector<int> W) {
    n = N;
    m = M;
    w = W;

    iota(id, id + M, 0);
    sort(id, id + M, [&](int i, int j) {
        return w[i] < w[j];
    });

    init(N);
    for (int i = 0; i < M; ++i) {
        int j = id[i];
        uset(u[j], v[j]);
    }
}

int getMinimumFuelCapacity(int u, int v) {
    int l = 0, r = m - 1, ans = -1;

    while (l <= r) {
        int mid = (l + r) >> 1;
        int x = fset(u, mid);
        int y = fset(v, mid);

        if (x == y) {
            auto it = --upper_bound(all(max_deg[x]), make_pair(mid + 1, -1));

            if (cycled(x, mid) || (it -> second) > 2) {
                ans = w[id[mid]];
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        } else {
            l = mid + 1;
        }
    }

    return ans;
}

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