제출 #878340

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
878340		boris_mihov	자매 도시 (APIO20_swap)	C++17	100 / 100	333 ms	49056 KiB

swap

#include "swap.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>
 
typedef long long llong;
const int MAXN = 100000 + 10;
const int MAXLOG = 17;
const int INF  = 2e9;

int n, m;
struct Sparse
{
    int par[MAXLOG][MAXN];
    int max[MAXLOG][MAXN];
    int dep[MAXN];

    void build(int p[], int e[], int d[])
    {
        for (int i = 1 ; i <= n ; ++i)
        {
            par[0][i] = p[i];
            max[0][i] = e[i];
            dep[i] = d[i];
        }

        for (int log = 1 ; (1 << log) <= n ; ++log)
        {
            for (int i = 1 ; i <= n ; ++i)
            {
                par[log][i] = par[log - 1][par[log - 1][i]];
                max[log][i] = std::max(max[log - 1][i], max[log - 1][par[log - 1][i]]);
            }
        }
    }

    void equalize(int &u, int v, int &res)
    {
        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (dep[par[log][u]] >= dep[v])
            {
                res = std::max(res, max[log][u]);
                u = par[log][u];
            }
        }
    }

    void calcLCA(int &u, int v, int &res)
    {
        if (u == v)
        {
            return;
        }

        for (int log = MAXLOG - 1 ; log >= 0 ; --log)
        {
            if (par[log][u] != par[log][v])
            {
                res = std::max(res, max[log][u]);
                res = std::max(res, max[log][v]);
                u = par[log][u];
                v = par[log][v];
            }
        }

        res = std::max(res, max[0][v]);
        res = std::max(res, max[0][u]);
        u = par[0][u];
    }

    int findLCA(int u, int v)
    {
        int res = 0;
        if (dep[u] < dep[v])
        {
            std::swap(u, v);
        }

        equalize(u, v, res);
        calcLCA(u, v, res);
        return u;
    }

    int findMAX(int u, int v)
    {
        int res = 0;
        if (dep[u] < dep[v])
        {
            std::swap(u, v);
        }

        equalize(u, v, res);
        calcLCA(u, v, res);
        return res;
    }
};

struct DSU
{
    int par[MAXN];
    int dep[MAXN];

    void build()
    {
        std::iota(par + 1, par + 1 + n, 1);
        std::fill(dep + 1, dep + 1 + n, 1);
    }

    int find(int node)
    {
        if (par[node] == node) return node;
        return par[node] = find(par[node]);
    }

    void connect(int u, int v)
    {
        u = find(u);
        v = find(v);

        if (u == v)
        {
            return;
        }

        if (dep[u] > dep[v])
        {
            std::swap(u, v);
        }

        if (dep[u] == dep[v])
        {
            dep[v]++;
        }

        par[u] = v;
    }

    bool areConnected(int u, int v)
    {
        return find(u) == find(v);
    }
};

struct Edge
{
    int u, v;
    int dist;

    friend bool operator < (const Edge &a, const Edge &b)
    {
        return a.dist < b.dist;
    }
};

int p[MAXN];
int e[MAXN];
int dep[MAXN];
int minD[MAXN];
bool vis[MAXN];
std::priority_queue <std::pair <int,int>> relax;
std::vector <std::pair <int,int>> g[MAXN];
std::vector <std::pair <int,int>> t[MAXN];
std::vector <Edge> edges;
Sparse sparse;
DSU dsu;

void buildDFS(int node, int par)
{
    p[node] = par;
    dep[node] = dep[par] + 1;

    for (const auto &[u, d] : t[node])
    {
        if (u == par)
        {
            continue;
        }

        e[u] = d;
        buildDFS(u, node);
    }
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) 
{
    n = N; m = M;
    for (int i = 0 ; i < M ; ++i)
    {
        U[i]++; V[i]++;
        g[U[i]].emplace_back(V[i], W[i]);
        g[V[i]].emplace_back(U[i], W[i]);
        edges.push_back({U[i], V[i], W[i]});
    }

    std::fill(minD + 1, minD + 1 + n, INF);
    for (int i = 1 ; i <= n ; ++i)
    {
        std::sort(g[i].begin(), g[i].end(), [&](auto x, auto y)
        {
            return x.second < y.second;
        });

        if (g[i].size() >= 3)
        {
            minD[i] = g[i][2].second;
        }
    }

    dsu.build();
    std::sort(edges.begin(), edges.end());
    for (const auto &[u, v, d] : edges)
    {
        if (dsu.areConnected(u, v))
        {
            minD[u] = std::min(minD[u], d);
            minD[v] = std::min(minD[v], d);
        } else
        {
            t[u].emplace_back(v, d);
            t[v].emplace_back(u, d);
            dsu.connect(u, v);
        }
    }

    buildDFS(1, 0);
    sparse.build(p, e, dep);

    for (int i = 1 ; i <= n ; ++i)
    {
        relax.push({-minD[i], i});
    }
    
    while (!relax.empty())
    {
        auto [dist, node] = relax.top();
        relax.pop();

        if (vis[node])
        {
            continue;
        }

        vis[node] = true;
        for (const auto &[u, d] : t[node])
        {
            if (minD[u] > std::max(minD[node], d))
            {
                minD[u] = std::max(minD[node], d);
                relax.push({-minD[u], u});
            }
        }
    }
}
 
int getMinimumFuelCapacity(int x, int y) 
{
    x++; y++;
    int res = sparse.findMAX(x, y);
    res = std::max(res, minD[x]);
    res = std::max(res, minD[y]);
    if (res == INF) return -1;
    return res;
}

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