제출 #597257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
597257		Ozy	자매 도시 (APIO20_swap)	C++17	37 / 100	2084 ms	15164 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 u second.first
#define v second.second
#define w first

lli n,m,a,b,c,dis,cont;
vector<pair<lli,pair<lli,lli> > > orden;
pair<lli,lli> uf[MAX+2];
lli grado[MAX+2],ciclo[MAX+2];

lli sube(lli act) {
    if (uf[act].first == act) return act;
    uf[act].first = sube(uf[act].first);
    return uf[act].first;
}

void une(lli a, lli b) {
    uf[b].first = a;
    uf[a].second = max(uf[a].second, uf[b].second);
    if (ciclo[b]) ciclo[a] = 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());
}

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

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

    for (auto act : orden) {
        cont++;

        a = sube(act.u);
        b = sube(act.v);
        grado[act.u]++;
        grado[act.v]++;

        if (a != b) une(a,b);
        else ciclo[a] = 1;

        if (grado[act.u] > uf[a].second) uf[a].second = grado[act.u];
        if (grado[act.v] > uf[a].second) uf[a].second = grado[act.v];

        a = sube(X);
        b = sube(Y);

        if (a == b) {
            if (uf[a].second > 2 || ciclo[a]) return act.w;
        }
    }

    return -1;
}

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