제출 #1199035

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199035		browntoad	자매 도시 (APIO20_swap)	C++20	17 / 100	2095 ms	11888 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// #define int ll
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, n+1)
#define RREP(i, n) for (int i = (n)-1; i >= 0; i--)
#define pii pair<int, int>
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())

struct Edge{
    int u, v, w;
};
namespace{
    int n, m;
    const ll maxn = 1e5+5;
    vector<pii> g[maxn];
    vector<int> par(maxn), dg(maxn);
    vector<Edge> ee;
}

int fin(int a){
    if (a == par[a]) return a;
    return par[a] = fin(par[a]);
}
void merg(int a, int b){
    a = fin(a); b = fin(b);
    par[a] = b;
}

bool cmp(Edge a, Edge b){
    return a.w < b.w;
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M;
    REP(i, m){
        g[U[i]].pb({V[i], W[i]});
        g[V[i]].pb({U[i], W[i]});
        ee.pb({U[i], V[i], W[i]});
    }
    sort(ALL(ee), cmp);
}

int getMinimumFuelCapacity(int X, int Y) {
    REP(i, n) par[i] = i;
    REP(i, n) dg[i] = 0;

    for (auto e:ee){
        dg[e.u]++;
        dg[e.v]++;
        merg(e.u, e.v);
        if (fin(X) != fin(Y)) continue;
        bool ex1 = 0;
        REP(i, n){
            if (fin(i) == fin(X)){
                if (dg[i] >= 3) return e.w;
                if (dg[i] == 1) ex1 = 1;
            }
        }
        if (!ex1) return e.w;
    }
    return -1;
    
}

/*
5 4
0 1 3
0 2 4
0 3 5
0 4 6
10
0 1
0 2
0 3
0 4
1 2
1 3
1 4
2 3
2 4
3 4
*/

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