Submission #333433

#	Time	Username	Problem	Language	Result	Execution time	Memory
333433		534351	자매 도시 (APIO20_swap)	C++17	100 / 100	673 ms	50900 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>

using namespace std;
// using namespace __gnu_pbds;

// template<class T>
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 100013;
const int INF = 1e9 + 7;

int N, T;
int dsu[MAXN];
vpi edge[MAXN];
int t[MAXN];
pii corners[MAXN];
vi nodes[MAXN];
bitset<MAXN> ok;
int st[MAXN], ft[MAXN];
pii jump[20][MAXN];

bool insubt(int u, int v) //is v in the subtree of u?
{
    return (u == N || (st[u] <= st[v] && st[v] <= ft[u]));
}
void dfs(int u, int p)
{
    st[u] = T;
    ft[u] = T;
    T++;
    for (auto e : edge[u])
    {
        int d = e.fi, v = e.se;
        if (v == p) continue;
        jump[0][v] = {u, d};
        dfs(v, u);
        ft[u] = ft[v];
    }
}
int get(int u)
{
    return (u == dsu[u] ? u : dsu[u] = get(dsu[u]));
}
void init(int n, int m, vi U, vi V, vi W)
{
    N = n;
    fill(t, t + N, INF);
    vector<pair<int, pii> > edges(m);
    FOR(i, 0, m)
    {
        edges[i] = {W[i], {U[i], V[i]}};
    }
    sort(ALL(edges));
    FOR(i, 0, N)
    {
        dsu[i] = i;
        nodes[i].PB(i);
        corners[i] = {i, i};
    }
    for (auto e : edges)
    {
        int d = e.fi, u = e.se.fi, v = e.se.se;
        int cu = get(u), cv = get(v);
        if (cu == cv)
        {
            if (!ok[cu])
            {
                for (int w : nodes[cu]) t[w] = d;
                ok[cu] = true;
            }
            //they're in the same component.
        }
        else
        {
            edge[u].PB({d, v});
            edge[v].PB({d, u});
            // cerr << "EDGE " << u << " <-> " << v << ' ' << d << endl;
            if (SZ(nodes[cu]) < SZ(nodes[cv]))
            {
                swap(u, v);
                swap(cu, cv);
            }
            //they're in different components.
            bool bad = (!ok[cu] && !ok[cv]
            && (u == corners[cu].fi || u == corners[cu].se) && (v == corners[cv].fi || v == corners[cv].se));
            if (bad) //update corners
            {
                pii corn = {corners[cu].fi ^ corners[cu].se ^ u, corners[cv].fi ^ corners[cv].se ^ v};
                corners[cu] = corn;
            }
            else //mark anybody that needs to be marked.
            {
                if (!ok[cu])
                {
                    for (int w : nodes[cu]) t[w] = d;
                }
                if (!ok[cv])
                {
                    for (int w : nodes[cv]) t[w] = d;
                }
                ok[cu] = true;
            }
            nodes[cu].insert(nodes[cu].end(), ALL(nodes[cv]));
            nodes[cv].clear();
            dsu[cv] = cu;
        }
    }
    jump[0][N] = {N, 0};
    jump[0][0] = {N, 0};
    dfs(0, N);
    FOR(i, 1, 20)
    {
        FOR(j, 0, N + 1)
        {
            jump[i][j] = {jump[i - 1][jump[i - 1][j].fi].fi, max(jump[i - 1][j].se, jump[i - 1][jump[i - 1][j].fi].se)};
        }
    }
    //now you want to be able to find longest edge on path u to v
}
int ask(int u, int v)
{
    // cerr << "ASK " << u << ' ' << v << endl;
    int res = 0;
    FORD(i, 20, 0)
    {
        if (insubt(jump[i][u].fi, v)) continue;
        ckmax(res, jump[i][u].se);
        u = jump[i][u].fi;
    }
    if (!insubt(u, v))
    {
        ckmax(res, jump[0][u].se);
    }
    FORD(i, 20, 0)
    {
        if (insubt(jump[i][v].fi, u)) continue;
        ckmax(res, jump[i][v].se);
        v = jump[i][v].fi;
    }
    if (!insubt(v, u))
    {
        ckmax(res, jump[0][v].se);
    }
    return res;
}

int getMinimumFuelCapacity(int u, int v)
{
    // cerr << "ASK " << ask(u, v) << endl;
    int res = max(ask(u, v), max(t[u], t[v]));
    if (res == INF) res = -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