Submission #597749

#	Time	Username	Problem	Language	Result	Execution time	Memory
597749		Ozy	Swapping Cities (APIO20_swap)	C++17	100 / 100	186 ms	22992 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 100000
#define w first
#define u second.first
#define v second.second

struct x{
    lli padre;
    lli flag;
    lli prof;
    lli val;
    lli l;
    lli r;
};

lli dis[MAX+2];
lli n,m,a,b,res;
vector< pair<lli, pair<lli,lli> > >  orden;
x uf[MAX+2];

lli dfs(lli pos) {
    if (dis[pos] > 0) return dis[pos]+1;
    if (uf[pos].padre == pos) {
        dis[pos] = 1;
        return 2;
    }
    dis[pos] = dfs(uf[pos].padre);
    return dis[pos]+1;
}

void init(int N, int M,std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N;
    m = M;

    rep(i,0,m-1) orden.push_back({W[i], {U[i]+1,V[i]+1} });
    sort(orden.begin(), orden.end());

    rep(i,1,n) uf[i] = {i,0,1,0,i,i};

    for (auto act : orden) {

        a = uf[act.u].padre;
        while (a != uf[a].padre) a = uf[a].padre;
        b = uf[act.v].padre;
        while (b != uf[b].padre) b = uf[b].padre;

        if (a == b) {
            if (uf[a].flag) continue;
            uf[a].flag = act.w;
        }
        else {

            if (uf[b].prof > uf[a].prof) {
                swap(a,b);
                swap(act.u, act.v);
            }

            uf[b].val = act.w;
            uf[b].padre = a;
            if (uf[b].prof == uf[a].prof) uf[a].prof++;

            if (uf[a].flag) continue;

            if (uf[b].flag) uf[a].flag = act.w;
            else {

                if (uf[a].l == act.u && uf[b].l == act.v) uf[a].l = uf[b].r;
                else if (uf[a].l == act.u && uf[b].r == act.v) uf[a].l = uf[b].l;
                else if (uf[a].r == act.u && uf[b].l == act.v) uf[a].r = uf[b].r;
                else if (uf[a].r == act.u && uf[b].r == act.v) uf[a].r = uf[b].l;
                else {
                     uf[a].flag = act.w;
                }

            }


        }

    }

    rep(i,1,n) if (dis[i] == 0) {
        if (uf[i].padre == i) dis[i] = 1;
        else dis[i] = dfs(uf[i].padre);
    }
}

int getMinimumFuelCapacity(int X, int Y) {
    X++;
    Y++;

    if (dis[X] < dis[Y]) swap(X,Y);
    a = dis[X] - dis[Y];

    res = -1;
    rep(i,1,a) {
        res = max(res,uf[X].val);
        X = uf[X].padre;
    }

    while (X != Y) {
        res = max(res,uf[X].val);
        X = uf[X].padre;
        res = max(res,uf[Y].val);
        Y = uf[Y].padre;
    }

    while (uf[X].flag == 0) {
        res = max(res,uf[X].val);
        if (X != uf[X].padre) X = uf[X].padre;
        else return -1;
    }

    res = max(res,uf[X].flag);
    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