제출 #697583

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697583		whqkrtk04	자매 도시 (APIO20_swap)	C++17	37 / 100	2086 ms	11320 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> plll;
#define fi first
#define se second
const int INF = 1e9+1;
const int P = 1000000007;
const ll LLINF = (ll)1e18+1;
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) { os << p.fi << " " << p.se; return os; }
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) { for(auto i : v) os << i << " "; os << "\n"; return os; }

struct UF {
    vector<int> P, A, B, C;

    int fin(int x) {
        if(P[x] == x) return x;
        else return P[x] = fin(P[x]);
    }

    int max_deg(int x) {
        return B[fin(x)];
    }

    void mer(int x, int y) {
        //cout << x << " " << y << "\n";
        int xx = fin(x), yy = fin(y);
        if(xx != yy) P[yy] = xx;
        else C[xx] = 1;
        B[xx] = max(max(B[xx], B[yy]), max(++A[x], ++A[y]));
        C[xx] = C[xx] || C[yy];
    }

    UF(int n) {
        A.resize(n, 0), B.resize(n, 0), C.resize(n, 0);
        for(int i = 0; i < n; i++) P.push_back(i);
    }
};

int n, m;
vector<piii> E;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N, m = M, E.resize(M);
    for(int i = 0; i < M; i++) E[i] = {W[i], {U[i], V[i]}};
    sort(E.begin(), E.end());
}

int getMinimumFuelCapacity(int X, int Y) {
    UF uf(n);
    for(int i = 0; i < m; i++) {
        uf.mer(E[i].se.fi, E[i].se.se);
        //cout << uf.A << uf.B << uf.C << uf.P << "\n";
        if(uf.fin(X) == uf.fin(Y) && (uf.B[uf.fin(X)] >= 3 || uf.C[uf.fin(X)])) return E[i].fi;
    }
    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