Submission #1000342

#	Time	Username	Problem	Language	Result	Execution time	Memory
1000342		underwaterkillerwhale	Swapping Cities (APIO20_swap)	C++17	17 / 100	250 ms	524288 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 1e5 + 7;
const int Mod = 1e9 +7;
const int szBL = 400;
const int INF = 1e9;
const int BASE = 137;

struct Edge {
    int u, v, w;
};

vector<int> weights;
struct Data {
    int labu, labv, szu, szv;
    bool islineu, islinev;
    pair<int,int> lnu, lnv;
};

struct Disjoin_set {
    int lab[N], sz[N];
    bool isline[N];
    pair<int,int> ln[N];

    stack<Data> op;
    void init (int n) {
        rep (i, 1, n) {
            lab[i] = i;
            sz[i] = 1;
            isline[i] = 1;
            ln[i] = {i, i};
        }
    }

    int Find (int u) {
        return u == lab[u] ? u : Find(lab[u]);
    }

    void Join (int u, int v){
        int uu = u, vv = v;
        u = Find(u);
        v = Find(v);
        op.push({u,v, sz[u], sz[v], isline[u], isline[v], ln[u], ln[v]});
        if (u == v) {
            isline[u] = 0;
            return;
        }
        if (sz[u] < sz[v]) swap (u, v), swap (uu, vv);
        if (min(isline[v], isline[u]) == 0) {
            isline[u] = isline[v] = 0;
        }
        else {
            if ((uu != ln[u].fs && uu != ln[u].se) || (vv != ln[v].fs && vv != ln[v].se)) {
                isline[u] = isline[v] = 0;
            }
            else {
                static vector<int> vec;
                if (ln[u].fs == ln[u].se) {
                    if (ln[v].fs != vv) ln[u].se = ln[v].fs;
                    else ln[u].se = ln[v].se;
                }
                else if (ln[v].fs == ln[v].se) {
                    if (ln[u].fs != uu) ln[u].se = ln[v].fs;
                    else ln[u].fs = ln[v].fs;
                }
                else {
                    vec = {ln[u].fs, ln[u].se, ln[v].fs, ln[v].se};
                    ln[u] = {-1, -1};
                    iter (&id, vec) {
                        if (id != uu && id != vv) {
                            if (ln[u].fs == -1) ln[u].fs = id;
                            else ln[u].se = id;
                        }
                    }
                }
            }
        }
        lab[v] = u;
        sz[u] += sz[v];
    }

    void roll_back() {
        Data &cur = op.top();
        op.pop();
        int u = cur.labu, v = cur.labv;
        lab[u] = cur.labu;
        sz[u] = cur.szu;
        isline[u] = cur.islineu;
        ln[u] = cur.lnu;

        lab[v] = cur.labv;
        sz[v] = cur.szv;
        isline[v] = cur.islinev;
        ln[v] = cur.lnv;

    }

    bool check (int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u != v) return 0;
        return isline[u] == 0;
    }

}DSU[szBL + 2];

int n, m, Q;
vector<Edge> edges;
map<pair<int,int>, int> Ans;

///0-idxed
int getBL (int X) { return X / szBL; }
int getLf (int X) { return X * szBL; }
int getRt (int X) { return min(m, (X + 1) * szBL - 1); }

void algo() {
    sort (ALL(edges), [] (Edge A, Edge B) { return A.w < B.w; });
    rep (bl, 0, getBL(m)) {
        if (bl == 0) DSU[bl].init(n);
        else {
            DSU[bl] = DSU[bl - 1];
            stack<Data> ().swap(DSU[bl].op);
        }
        rep (i, getLf(bl), getRt(bl)) {
            DSU[bl].Join(edges[i].u, edges[i].v);
        }
    }
}

int getMinimumFuelCapacity (int X, int Y) {
    ++X, ++Y;
    reb (bl, getBL(m), 0){
        if (DSU[bl].check(X, Y) == 0) {
            if (bl == getBL(m)) return -1;
            Disjoin_set &cur = DSU[bl];
            rep (i, getLf(bl + 1), getRt(bl + 1)) {
                cur.Join(edges[i].u, edges[i].v);
                if (cur.check(X, Y)) {
                    reb (j, i, getLf(bl + 1)) cur.roll_back();
                    return edges[i].w;
                }
            }
        }
        else if (bl == 0 && DSU[bl].check(X, Y) == 1) {
            Disjoin_set &cur = DSU[bl];
            int numdel = 0;
            while (cur.check(X, Y)) ++numdel, cur.roll_back();
            rep (i, getRt(bl) - numdel + 1, getRt(bl)) {
                cur.Join(edges[i].u, edges[i].v);
            }
            return edges[getRt(bl) - numdel + 1].w;
        }
    }
    return -1;
}

void init (int _n, int _m, vector<int> _U, vector<int> _V, vector<int> _W) {
//void solution() {
    n = _n;
    m = _m;
    rep (i, 0, m  - 1) {
        int u = _U[i], v = _V[i], w = _W[i];
        ++u, ++v;
        edges.push_back({u, v, w});
    }
//    cin >> n >> m;
//    rep (i, 1, m) {
//        int u, v, w;
//        cin >> u >> v >> w;
//        ++u,++v;
//        edges.push_back({u, v, w});
//    }
    algo();
//    cin >> Q;
//    rep (i, 1, Q) {
//        int X, Y;
//        cin >> X >> Y;
//        cout << getMinimumFuelCapacity(X, Y) <<"\n";
//    }
}

//#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
//int main () {
//    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
////    file ("c");
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1




3 2
0 1 5
0 2 5
1
1 2

*/

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