Submission #999921

#	Time	Username	Problem	Language	Result	Execution time	Memory
999921		underwaterkillerwhale	Swapping Cities (APIO20_swap)	C++17	37 / 100	2098 ms	17348 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  = 2e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const int INF = 1e9;
const int BASE = 137;

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

vector<int> weights;

struct Query {
    int X, Y;
    int id;
    int lf, rt, ok;
    int getMid() { return lf + rt >> 1; }
};

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

    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 : lab[u] = Find(lab[u]);
    }

    void Join (int u, int v){
        int uu = u, vv = v;
        u = Find(u);
        v = Find(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];
    }
    bool check (int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u != v) return 0;
        return isline[u] == 0;
    }
}DSU;

int n, m, Q;
vector<Edge> edges;
Query qr[N];
map<pair<int,int>, int> Ans;

void algo() {
    sort (ALL(edges), [] (Edge A, Edge B) { return A.w < B.w; });
    iter (&E, edges) weights.push_back(E.w);
    sort (ALL(weights));
    weights.resize (unique(ALL(weights)) - weights.begin());
    rep (i, 1, Q) {
        qr[i].lf = 0;
        qr[i].rt = SZ(weights) - 1;
        qr[i].ok = 0;
    }

    rep (step, 0, 25) {
        DSU.init(n);
        sort (qr + 1, qr + 1 + Q, [] (Query A, Query B) { return A.getMid() < B.getMid(); });
        int ptrQ = 1, ptrE = 0;
        iter (&W, weights) {
            while (ptrE < SZ(edges) && edges[ptrE].w < W) ++ptrE;
            while (ptrQ <= Q && weights[qr[ptrQ].getMid()] < W) ++ptrQ;
            while (ptrE < SZ(edges) && edges[ptrE].w == W)  {
                Edge &cur = edges[ptrE];
                DSU.Join(cur.u, cur.v);
                ++ptrE;
            }
            while (ptrQ <= Q && weights[qr[ptrQ].getMid()] == W) {
                Query &cur = qr[ptrQ];
                if (DSU.check(cur.X, cur.Y)) {
                    qr[ptrQ].rt = qr[ptrQ].getMid();
                    qr[ptrQ].ok = 1;
                }
                else qr[ptrQ].lf = qr[ptrQ].getMid() + 1;
                ++ptrQ;
            }
        }
    }
    sort (qr + 1, qr + 1 + Q, [] (Query A, Query B) { return A.id < B.id; });
//    rep (i, 1, Q) {
//        if (qr[i].ok == 1) {
////            cout << weights[qr[i].getMid()] <<"\n";
//            Ans[mp(qr[i].X, qr[i].Y)] = weights[qr[i].getMid()];
//        }
//        else {
//            Ans[mp(qr[i].X, qr[i].Y)] = -1;
////            cout << -1 <<"\n";
//        }
//    }
}

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

int getMinimumFuelCapacity (int X, int Y) {
    Q = 1;
    qr[1].X = ++X, qr[1].Y = ++Y;
    algo();
    if (qr[1].ok == 1) 
////            cout << weights[qr[i].getMid()] <<"\n";
        return weights[qr[1].getMid()];
    else return -1;
//            Ans[mp(qr[i].X, qr[i].Y)] = weights[qr[i].getMid()];
//        }
//        else {
//            Ans[mp(qr[i].X, qr[i].Y)] = -1;
////            cout << -1 <<"\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

*/

Compilation message (stderr)

swap.cpp: In member function 'int Query::getMid()':
swap.cpp:39:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |     int getMid() { return lf + rt >> 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