제출 #465983

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
465983		alextodoran	자매 도시 (APIO20_swap)	C++17	36 / 100	692 ms	48020 KiB

swap

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

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

using namespace std;

typedef long long ll;

const int INF = INT_MAX / 2;

struct Edge
{
    int u, v;
    int w;

    int other (int x)
    {
        return (u ^ v ^ x);
    }

    bool primary;
};

int N, M;

vector <Edge> edges;

vector <vector <Edge*>> adj;

vector <int> special;
vector <int> cost;

vector <int> parent;
vector <int> parw;
vector <int> depth;

int BITS;

vector <vector <int>> anc;
vector <vector <int>> ancw;

int ancestor (int &u, int k)
{
    int maxw = 0;
    for(int bit = BITS - 1; bit >= 0; bit--)
        if((k >> bit) & 1)
        {
            maxw = max(maxw, ancw[u][bit]);
            u = anc[u][bit];
        }
    return maxw;
}

int dist (int u, int v)
{
    int maxw = 0;
    if(depth[u] > depth[v])
        maxw = max(maxw, ancestor(u, depth[u] - depth[v]));
    if(depth[v] > depth[u])
        maxw = max(maxw, ancestor(v, depth[v] - depth[u]));

    if(u == v)
        return maxw;

    for(int bit = BITS - 1; bit >= 0; bit--)
        if(anc[u][bit] != anc[v][bit])
        {
            maxw = max(maxw, ancw[u][bit]);
            maxw = max(maxw, ancw[v][bit]);
            u = anc[u][bit];
            v = anc[v][bit];
        }
    maxw = max(maxw, parw[u]);
    maxw = max(maxw, parw[v]);

    return maxw;
}

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

    /// Process edges

    edges = vector <Edge> (M);
    for(int i = 0; i < M; i++)
        edges[i] = Edge{U[i], V[i], W[i], false};

    adj = vector <vector <Edge*>> (N);
    for(int i = 0; i < M; i++)
    {
        adj[edges[i].u].push_back(&edges[i]);
        adj[edges[i].v].push_back(&edges[i]);
    }

    /// Use DSU to find minimum spanning tree

    {
        vector <int> par (N);
        for(int u = 0; u < N; u++)
            par[u] = u;

        function <int (int)> findRoot = [&] (int u)
        {
            if(par[u] == u)
                return u;
            return par[u] = findRoot(par[u]);
        };
        function <bool (int, int)> join = [&] (int u, int v)
        {
            u = findRoot(u);
            v = findRoot(v);

            if(u == v)
                return false;

            par[u] = v;
            return true;
        };

        // Sort edges by weight

        vector <int> edgeOrder (M);
        for(int i = 0; i < M; i++)
            edgeOrder[i] = i;
        sort(edgeOrder.begin(), edgeOrder.end(),
             [&] (const int &x, const int &y)
             {
                 return edges[x].w < edges[y].w;
             });

        // Find "primary" edges that form the spanning tree

        for(int j = 0; j < M; j++)
        {
            int i = edgeOrder[j];
            if(join(edges[i].u, edges[i].v) == true)
                edges[i].primary = true;
        }
    }

    /// Use DFS to find the structure of the tree

    parent = vector <int> (N, -1);
    parw = vector <int> (N, 0);
    depth = vector <int> (N, 0);

    vector <bool> visited (N, false);

    function <void (int)> dfs = [&] (int u)
    {
        visited[u] = true;
        for(Edge* e : adj[u])
            if(e->primary == true)
            {
                int v = e->other(u);
                if(visited[v] == false)
                {
                    depth[v] = depth[u] + 1;
                    parent[v] = u;
                    parw[v] = e->w;

                    dfs(v);
                }
            }
    };

    for(int u = 0; u < N; u++)
        if(visited[u] == false)
            dfs(u);

    /// Use binary lifting to get ancestors and be able to compute distance

    BITS = 0;
    while((1 << BITS) <= N)
        BITS++;

    anc = vector <vector <int>> (N, vector <int> (BITS, -1));
    ancw = vector <vector <int>> (N, vector <int> (BITS, 0));

    for(int u = 0; u < N; u++)
    {
        anc[u][0] = parent[u];
        ancw[u][0] = parw[u];
    }
    for(int bit = 1; bit < BITS; bit++)
        for(int u = 0; u < N; u++)
        {
            if(anc[u][bit - 1] != -1)
            {
                anc[u][bit] = anc[anc[u][bit - 1]][bit - 1];
                ancw[u][bit] = max(ancw[u][bit - 1], ancw[anc[u][bit - 1]][bit - 1]);
            }
        }

    /// Find special cost for each node

    // Intersection nodes

    special = vector <int> (N, INF);
    for(int u = 0; u < N; u++)
        if((int) adj[u].size() >= 3)
        {
            vector <int> aux;
            for(Edge* e : adj[u])
                aux.push_back(e->w);
            sort(aux.begin(), aux.end());

            special[u] = aux[2];
        }

    // Cycle nodes

    for(int i = 0; i < M; i++)
        if(edges[i].primary == false)
            special[edges[i].u] = edges[i].w;

    /// Use DSU to find additional cost for each node

    {
        vector <int> par (N);
        for(int u = 0; u < N; u++)
            par[u] = u;
        vector <int> wpar (N, 0);
        vector <int> dim (N, 1);
        vector <int> minCost (N, INF);

        function <int (int)> findRoot = [&] (int u)
        {
            if(par[u] == u)
                return u;
            return findRoot(par[u]);
        };
        function <void (int, int, int)> join = [&] (int u, int v, int w)
        {
            u = findRoot(u);
            v = findRoot(v);

            if(u == v)
                return;

            if(dim[u] > dim[v])
                swap(u, v);

            par[u] = v;
            wpar[u] = w;
            dim[v] += dim[u];
            if(minCost[v] == INF && minCost[u] != INF)
                minCost[v] = w;
        };

        vector <int> edgeOrder (M);
        for(int i = 0; i < M; i++)
            edgeOrder[i] = i;
        sort(edgeOrder.begin(), edgeOrder.end(),
             [&] (const int &x, const int &y)
             {
                 return edges[x].w < edges[y].w;
             });

        vector <int> specialOrder (N);
        for(int u = 0; u < N; u++)
            specialOrder[u] = u;
        sort(specialOrder.begin(), specialOrder.end(),
             [&] (const int &u, const int &v)
             {
                 return special[u] < special[v];
             });

        int currEdge = 0;
        int currSpecial = 0;

        while(currEdge < M || currSpecial < N)
        {
            if(currSpecial == N || (currEdge < M
               && edges[edgeOrder[currEdge]].w
                < special[specialOrder[currSpecial]]))
            {
                int i = edgeOrder[currEdge];
                join(edges[i].u, edges[i].v, edges[i].w);

                currEdge++;
            }
            else
            {
                int u = specialOrder[currSpecial];
                int r = findRoot(u);
                if(minCost[r] == INF)
                    minCost[r] = special[u];

                currSpecial++;
            }
        }

        cost = vector <int> (N);

        for(int u = 0; u < N; u++)
        {
            cost[u] = minCost[u];

            int v = u;
            int maxw = 0;
            while(par[v] != v)
            {
                maxw = max(maxw, wpar[v]);
                v = par[v];
                cost[u] = min(cost[u], max(maxw, minCost[v]));
            }
        }
    }

}

int getMinimumFuelCapacity (int U, int V)
{
    int answer = max(dist(U, V), cost[U]);
    if(answer == INF)
        return -1;
    return answer;
}

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