Submission #319974

#	Time	Username	Problem	Language	Result	Execution time	Memory
319974		arujbansal	Swapping Cities (APIO20_swap)	C++17	13 / 100	602 ms	32112 KiB

swap

    #include "swap.h"
    #include <bits/stdc++.h>
     
    #define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
    #define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
    #define pb push_back
    #define eb emplace_back
    #define all(x) (x).begin(), (x).end()
    #define rall(x) (x).rbegin(), (x).rend()
    #define sz(x) (int) (x).size()
    #define lc(i) 2*i
    #define rc(i) 2*i+1
    //#define int long long
    using namespace std;
    using ll = long long;
    using ii = pair<int, int>;
    using vii = vector<ii>;
    using vi = vector<int>;
    using vvi = vector<vi>;
    using vb = vector<bool>;
    using vvb = vector<vb>;
     
    const int MAXN = 1e5 + 20, MOD = 1e9 + 7, INF = 1e9;
     
    struct Edge {
        int u, v, w;
     
        bool operator<(const Edge &other) {
            return w < other.w;
        }
    };
     
    struct DSU {
        int n;
        vi par, s, deg, mxDeg, timeValid;
        vii root[MAXN];
        vi g[MAXN];
     
        void init(int n) {
            this->n = n;
            par.resize(n);
            iota(all(par), 0);
            s.assign(n, 1);
            deg.assign(n, 0);
            mxDeg.assign(n, 0);
            timeValid.assign(n, INF);
     
            for (int i = 0; i < n; i++)
                root[i].eb(0, i);
        }
     
        int get(int x) {
            return par[x];
        }
     
        void mark(int x, int newPar, int time) {
            if (par[x] == newPar) return;
     
            par[x] = newPar;
            root[x].eb(time, newPar);
     
            for (const auto &v : g[x]) mark(v, newPar, time);
        }
     
        void unite(int u, int v, int time) {
            g[u].pb(v);
            g[v].pb(u);
            
            deg[u]++;
            deg[v]++;
     
            int x = get(u);
            int y = get(v);
     
            if (deg[u] >= 3) timeValid[x] = min(timeValid[x], time);
            if (deg[v] >= 3) timeValid[y] = min(timeValid[y], time);
     
            if (x == y) {
                timeValid[x] = min(timeValid[x], time);
                return;
            }
     
            if (s[x] > s[y]) {
                swap(x, y);
                swap(u, v);
            }
     
            s[y] += s[x];
            timeValid[y] = min(timeValid[y], timeValid[x]);
          	mark(par[x], y, time);
        }
     
        bool query(int u, int v, int time) {
            time++;
     
            auto x = upper_bound(all(root[u]), ii(time, INF));
            auto y = upper_bound(all(root[v]), ii(time, INF));
            x--, y--;
     
            ii rootU = *x;
            ii rootV = *y;
     
            if (rootU.second == rootV.second)
                return timeValid[rootU.second] <= time;
     
            return false;
        }
    };
     
    DSU graph;
    vector<Edge> edges;
    int n, m;
     
    void init(int N, int M, vi U, vi V, vi W) {
        n = N;
        m = M;
     
        edges.resize(M);
     
        for (int i = 0; i < M; i++) {
            edges[i].u = U[i];
            edges[i].v = V[i];
            edges[i].w = W[i];
        }
     
        sort(all(edges));
     
        graph.init(N);
     
        for (int i = 0; i < M; i++)
            graph.unite(edges[i].u, edges[i].v, i + 1);
    }
     
    int getMinimumFuelCapacity(int X, int Y) {
        int lo = 0, hi = m - 1;
        int ans = INF;
     
        while (lo <= hi) {
            int mid = (lo + hi) >> 1;
            if (graph.query(X, Y, mid)) {
                ans = min(ans, edges[mid].w);
                hi = mid - 1;
            } else lo = mid + 1;
        }
     
        return ans < INF ? ans : -1;
    }
     
    //signed main() {
    //    FAST_IO;
    //#ifdef arujbansal_local
    //    setIO("input.txt", "output.txt");
    //#endif
    //
    //    int a, b;
    //    cin >> a >> b;
    //    int u[b], v[b], wt[b];
    //
    //    for (int i = 0; i < b; i++)
    //        cin >> u[i] >> v[i] >> wt[i];
    //
    //    init(a, b, u, v, wt);
    //
    //    int q;
    //    cin >> q;
    //    while (q--) {
    //        int x, y;
    //        cin >> x >> y;
    //        cout << getMinimumFuelCapacity(x, y) << "\n";
    //    }
    //
    ////    for (const auto &[time, root] : graph.root[4])
    ////        cout << time << " " << root << "\n";
    //}

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