제출 #319621

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
319621		VEGAnn	자매 도시 (APIO20_swap)	C++14	100 / 100	410 ms	49400 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define PB push_back
using namespace std;
const int N = 300100;
const int M = 200100;
const int PW = 20;
vector<int> g[N];
int n, m, U[M], V[M], W[M], pre[N], lst, indx[N], deg[N], cost[N];
int ht[N], up[N][PW], tin[N], tout[N], tt = 0, id[N];
bool mrk[N], good[N];

bool cmp(int _x, int _y){
    return (W[_x] < W[_y]);
}

int get(int x) { return (pre[x] == x ? x : pre[x] = get(pre[x])); }

void dfs(int v){
    tin[v] = tt++;

    for (int po = 1; po < PW; po++)
        up[v][po] = up[up[v][po - 1]][po - 1];

    for (int u : g[v]){
        ht[u] = ht[v] + 1;
        up[u][0] = v;

        dfs(u);
    }

    tout[v] = tt++;
}

void init(int NN, int MM, std::vector<int> UU, std::vector<int> VV, std::vector<int> WW) {
    n = NN; m = MM;

    for (int i = 0; i < m; i++) {
        U[i] = UU[i];
        V[i] = VV[i];
        W[i] = WW[i];
        id[i] = i;
    }

    for (int i = 0; i < n; i++) {
        pre[i] = i;
        indx[i] = i;
        good[i] = 0;
        deg[i] = 0;
    }

    sort(id, id + m, cmp);

    lst = n;

    for (int it = 0; it < m; it++){
        int i = id[it];

        int x = get(U[i]);
        int y = get(V[i]);

        if (x == y){
            if (!good[indx[x]]){
                g[lst].PB(indx[x]);
                good[lst] = 1;
                indx[x] = lst;
                cost[lst] = W[i];

                lst++;
            }
        } else {
            deg[U[i]]++;
            deg[V[i]]++;

            bool kok = (good[indx[x]] || good[indx[y]] || (deg[U[i]] > 2) || (deg[V[i]] > 2));

            g[lst].PB(indx[x]);
            g[lst].PB(indx[y]);
            cost[lst] = W[i];
            good[lst] = kok;
            indx[x] = lst;
            pre[y] = x;

            lst++;
        }
    }

    up[lst - 1][0] = lst - 1;
    dfs(lst - 1);
}

bool upper(int a, int b){
    return (tin[a] <= tin[b] && tout[b] <= tout[a]);
}

int lca(int a, int b){
    if (upper(a, b)) return a;
    if (upper(b, a)) return b;

    for (int po = PW - 1; po >= 0; po--)
        if (!upper(up[a][po], b))
            a = up[a][po];

    return up[a][0];
}

int getMinimumFuelCapacity(int X, int Y) {
    if (!good[lst - 1]) return -1;

    int lc = lca(X, Y);

    if (good[lc])
        return cost[lc];
    else {
        for (int po = PW - 1; po >= 0; po--){
            if (ht[lc] < (1 << po)) continue;

            if (!good[up[lc][po]])
                lc = up[lc][po];
        }

        return cost[up[lc][0]];
    }
}

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