제출 #964215

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964215		efedmrlr	자매 도시 (APIO20_swap)	C++17	7 / 100	1322 ms	35856 KiB

swap

// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include "swap.h"

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int ALPH = 26;
const int LGN = 20;
constexpr int MOD = 1e9+7;

struct Node {
    bool isl;
    array<int,2> e;
    int p;
    int sz;
    int ver;
    Node() {}
};

struct DSU {
    vector<Node> dt;
    int cnt = 0;
    void reset(int s) {
        dt.resize(s + 3);
    }
    void make_set(int x) {
        dt[x].p = x;
        dt[x].isl = 1;
        dt[x].e = {x, x};
        dt[x].sz = 1;
        dt[x].ver = cnt++;
    }
    int find_set(int x) {
        return (x == dt[x].p) ? x : dt[x].p = find_set(dt[x].p);
    }
    int union_set(int x, int y) {   // 0 nothing, 1 turned into non line, 2 merged as line, 3 merged and non line
        int a = x, b = y;
        x = find_set(x); y = find_set(y);
        dt[x].ver = dt[y].ver = cnt++;
        if(x == y) {
            dt[x].isl = 0;
            return 1;
        }
        if(dt[x].sz < dt[y].sz) {
            swap(x, y);
        }
        dt[x].sz += dt[y].sz;
        dt[y].p = x;
        if(dt[x].isl && dt[y].isl && (dt[x].e[0] == a || dt[x].e[1] == a) && (dt[y].e[0] == b || dt[y].e[1] == b)) {
            int en = dt[y].e[0];
            if(dt[y].e[0] == b) en = dt[y].e[1];
            if(dt[x].e[0] == a) dt[x].e[0] = en;
            else dt[x].e[1] = en; 
            
            return 2;
        } 
        else {
            dt[x].isl = 0;
            return 3;
        }
    }
};
int n,m,s;
vector<array<int,3> > edges;
vector<vector<int> > anc;
vector<int> cst;
vector<bool> stat;

void prec() {
    for(int k = 1; k < LGN; k++) {
        for(int i = 0; i < s; i++) {
            anc[i][k] = anc[anc[i][k - 1]][k - 1];
        }
    }
}
bool check(int val, int x, int y) {
    for(int k = LGN - 1; k >= 0; k--) {
        if(cst[anc[x][k]] <= val) {
            x = anc[x][k];
        }
        if(cst[anc[y][k]] <= val) {
            y = anc[y][k];
        }
    }
    // cout << x << " " << y << " xy" << endl;
    if(x != y) return 0;
    if(!stat[x]) return 0;
    return 1;
}

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
    n = N; m = M; s = N + M;
    edges.resize(M);
    REP(i,M) {
        edges[i] = {W[i], U[i], V[i]};
    }
    sort(all(edges));
    anc.assign(s, vector<int>(LGN, s - 1));
    cst.assign(s, 0);
    stat.assign(s, 0);

    DSU ds;
    ds.reset(n);
    REP(i,n) {
        stat[i] = 0;
        ds.make_set(i);
    }
    for(auto &c : edges) {
        anc[ds.dt[ds.find_set(c[1])].ver][0] = ds.cnt;
        anc[ds.dt[ds.find_set(c[2])].ver][0] = ds.cnt;
        int ret = ds.union_set(c[1], c[2]);
        if(ret & 1) {
            stat[ds.cnt - 1] = 1;
        }
        cst[ds.cnt - 1] = c[0];
        
    }
    // for(int i = 0; i < s ; i++) {
    //     cout << "i:" << i << " " << stat[i] << " " << cst[i] << "par: " << anc[i][0] << "\n";
    // }
    prec();
}

int getMinimumFuelCapacity(int X, int Y) {
    int tl = 0, tr = m - 1;
    while(tl < tr) {
        int tm = (tl + tr) >> 1;
        if(check(edges[tm][0], X, Y)) {
            tr = tm;
        }
        else {
            tl = tm + 1;
        }
    }
    if(!check(edges[tl][0], X, Y)) {
        tl++;
    }
    // cout << check(4, X, Y) << " val4" << endl;
    if(tl >= m) return -1; 
    return edges[tl][0];

}

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