제출 #558763

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
558763		Ai7081	자매 도시 (APIO20_swap)	C++17	6 / 100	533 ms	43052 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const bool debug = 1;

const int N = 1e5 + 5;
const int L = 20;
const int inf = 2e9;

struct edge{
    int u, v, w;
    bool operator < (const edge &o) const {return w<o.w;}
};

int n, m;
int p[N][L], ma[N][L], tin[N], tout[N];
int sz[N], dep[N], id[N], top[N], timer;
int root[N];
int t[4*N];
vector<pair<int, int>> adj[N];
vector<edge> back_edge, all_edge;

int findroot(int x) {return root[x]==x?x:root[x]=findroot(root[x]);}

int dfs(int v=0) {
    sz[v] = 1;
    tin[v] = ++timer;
    for (int i=1; i<L; i++) {
        p[v][i] = p[p[v][i-1]][i-1];
        ma[v][i] = max(ma[v][i-1], ma[p[v][i-1]][i-1]);
    }
    for (auto [to, w] : adj[v]) if (to!=p[v][0]) {
        p[to][0] = v;
        ma[to][0] = w;
        dep[to] = dep[v] + 1;
        sz[v] += dfs(to);
    }
    tout[v] = ++timer;
    return sz[v];
}

bool is_anc(int u, int v) {
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int lca(int u, int v) {
    int ret = -1;
    for (int i=L-1; i>=0; i--) if (!is_anc(p[u][i], v)) {
        ret = max(ret, ma[u][i]); u = p[u][i];
    }
    for (int i=L-1; i>=0; i--) if (!is_anc(p[v][i], u)) {
        ret = max(ret, ma[v][i]); v = p[v][i];
    }
    if (!is_anc(u, v)) ret = max(ret, ma[u][0]);
    if (!is_anc(v, u)) ret = max(ret, ma[v][0]);
    return ret;
}

void hld(int v=0, int tp=0) {
    id[v] = ++timer;
    top[v] = tp;
    int h_chi = -1, h_sz = -1;
    for (auto [to, w] : adj[v]) if (to!=p[v][0] && h_sz<sz[to]) h_sz = sz[to], h_chi = to;
    if (h_chi == -1) return;
    hld(h_chi, tp);
    for (auto [to, w] : adj[v]) if(to!=p[v][0] && to!=h_chi) hld(to, to);
}

void upd_seg(int l, int r, int val, int v=1, int tl=1, int tr=n) {
    if (tl > r || tr < l) return;
    if (l <= tl && tr <= r) {
        if (t[v] == -1) t[v] = val;
        return;
    }
    int tm = (tl+tr)/2;
    upd_seg(l, r, val, 2*v, tl, tm);
    upd_seg(l, r, val, 2*v+1, tm+1, tr);
}

int query_seg(int l, int r, int v=1, int tl=1, int tr=n) {
    if (tl > r || tr < l) return -1;
    if (l <= tl && tr <= r) return t[v];
    int tm = (tl+tr)/2;
    return max(t[v], max(query_seg(l, r, 2*v, tl, tm), query_seg(l, r, 2*v+1, tm+1, tr)));
}

void upd_path(int u, int v, int val) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        upd_seg(id[top[u]], id[u], val);
        u = p[top[u]][0];
    }
    if (u != v) {
        if (dep[u] > dep[v]) swap(u, v);
        upd_seg(id[u]+1, id[v], val);
    }
}

int query_path(int u, int v) {
    int ret = -1;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        ret = max(ret, query_seg(id[top[u]], id[u]));
        u = p[top[u]][0];
    }
    if (u != v) {
        if (dep[u] > dep[v]) swap(u, v);
        ret =  max(ret, query_seg(id[u]+1, id[v]));
    }
    return ret;
}

void init(int NN, int MM, vector<int> U, vector<int> V, vector<int> W)
{
    n = NN, m = MM;
    for (int i=0; i<m; i++) all_edge.push_back({U[i], V[i], W[i]});
    sort(all_edge.begin(), all_edge.end());
    for (int i=0; i<n; i++) root[i] = i;
    for (auto [u, v, w] : all_edge) {
        int ru = findroot(u), rv = findroot(v);
        if (ru == rv) back_edge.push_back({u, v, w});
        else root[rv] = ru, adj[u].push_back({v, w}), adj[v].push_back({u, w});
    }
    dfs();
    timer = 0;
    hld();
    fill_n(t, 4*N, -1);
    for (auto [u, v, w] : back_edge) upd_path(u, v, w);
}

int getMinimumFuelCapacity(int X, int Y)
{
    int res = query_path(X, Y);
    if (res == -1) return -1;
    return max(res, lca(X, Y));
}

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