제출 #674139

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
674139		ghostwriter	자매 도시 (APIO20_swap)	C++17	100 / 100	533 ms	49020 KiB

swap

#include "swap.h"

#include <vector>

// #pragma GCC optimize ("Ofast")
// #pragma GCC target ("avx2")
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
    #include <debug.h>
    #include "grader.cpp"
#else
    #define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
// #define int long long
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { T d2 = (a | b) & -(a | b); a /= d2; b /= d2; WHILE(b) { a = a % b; swap(a, b); } return a * d2; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
void _assert(bool statement) { if (statement) return; cerr << "\n>> Assertion failed!\n"; exit(0); }
void _assert(bool statement, const str &message) { if (statement) return; cerr << "\n>> Assertion failed: " << message << '\n'; exit(0); }
void _error(const str &message) { cerr << "\n>> Error: " << message << '\n'; exit(0); }
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    GOAT
----------------------------------------------------------------
*/
struct Edge {
    int u, v, w;
    Edge() {}
    Edge(int u, int v, int w) : u(u), v(v), w(w) {}
    bool operator <(const Edge &b) { return w < b.w; }
};
struct Status {
    int time, cnt[4];
    Status() { time = 0; memset(cnt, 0, sizeof cnt); }
};
const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;
int edgenum, p[MAXN], w1[MAXN], cpos[MAXN], d[MAXN];
Status csta[MAXN];
Edge e[MAXM];
vi vt[MAXN];
vpi pos[MAXN];
vector<Status> sta[MAXN];
void join(int u, int v, int w) {
    int un = cpos[u], vn = cpos[v];
    if (sz(vt[un]) < sz(vt[vn])) {
        swap(u, v);
        swap(un, vn);
    }
    if (un != vn) {
        EACH(i, vt[vn]) {
            vt[un].pb(i);
            pos[i].pb({w, un});
            cpos[i] = un;
        }
        FRN(i, 4) csta[un].cnt[i] += csta[vn].cnt[i];
    }
    --csta[un].cnt[min(d[u], 3)];
    --csta[un].cnt[min(d[v], 3)];
    ++d[u];
    ++d[v];
    ++csta[un].cnt[min(d[u], 3)];
    ++csta[un].cnt[min(d[v], 3)];
    sta[un].pb(Status());
    sta[un].bk().time = w;
    FRN(i, 4) sta[un].bk().cnt[i] = csta[un].cnt[i];
}
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    edgenum = M;
    FRN(i, M) w1[i] = W[i];
    sort(w1, w1 + M);
    w1[M] = -1;
    FRN(i, M) {
        W[i] = lb(w1, w1 + M, W[i]) - w1;
        e[i] = Edge(U[i], V[i], W[i]);
    }
    sort(e, e + M);
    FRN(i, N) {
        vt[i].pb(i);
        pos[i].pb({0, i});
        cpos[i] = i;
        csta[i].cnt[0] = 1;
    }
    FRN(i, M) {
        int u = e[i].u, v = e[i].v, w = e[i].w;
        join(u, v, w);
    }
}
int getp(int u, int time) {
    int l = 0, r = sz(pos[u]) - 1, ans = -1;
    WHILE(l <= r) {
        int mid = l + (r - l) / 2;
        if (pos[u][mid].st <= time) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return pos[u][ans].nd;
}
Status gets(int u, int time) {
    int l = 0, r = sz(sta[u]) - 1, ans = -1;
    WHILE(l <= r) {
        int mid = l + (r - l) / 2;
        if (sta[u][mid].time <= time) {
            ans = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return sta[u][ans];
}
bool check(int X, int Y, int time) {
    int px = getp(X, time), py = getp(Y, time);
    if (px != py) return 0;
    Status cur = gets(px, time);
    if (cur.cnt[3]) return 1;
    int total = 0; FRN(i, 4) total += cur.cnt[i];
    if (cur.cnt[2] == total - 2) return 0;
    return 1;
}
int getMinimumFuelCapacity(int X, int Y) {
    int l = 0, r = edgenum - 1, ans = edgenum;
    WHILE(l <= r) {
        int mid = l + (r - l) / 2;
        if (check(X, Y, mid)) {
            ans = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return w1[ans];
}
/*
3 2
0 1 5
0 2 5
1
1 2
*/

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