Submission #375386

#	Time	Username	Problem	Language	Result	Execution time	Memory
375386		rocks03	Swapping Cities (APIO20_swap)	C++14	100 / 100	671 ms	71596 KiB

swap

//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 5e5+100;
int dsu[MAXN], deg[MAXN], we[MAXN];
vector<int> g[MAXN];
bool dsu_c[MAXN], c[MAXN];

void init(int n){
    rep(i, 0, n){
        dsu[i] = i, dsu_c[i] = false, c[i] = false;
    }
}

int find(int x){
    if(x == dsu[x]) return x;
    dsu_c[dsu[x]] |= dsu_c[x];
    dsu[x] = find(dsu[x]);
    return dsu[x];
}

int root;
void unite(int a, int b, int w){
    a = find(a); b = find(b);
    dsu_c[root] = c[root] = (dsu_c[a] || dsu_c[b] || (a == b));
    we[root] = w;
    dsu[a] = root;
    g[root].pb(a);
    if(a != b){
        dsu[b] = root;
        g[root].pb(b);
    }
    root++;
}

const int MAXK = 20+5;
int dep[MAXN], p[MAXK][MAXN];

void dfs(int v, int pa){
    p[0][v] = pa;
    for(int u : g[v]){
        dep[u] = dep[v] + 1;
        dfs(u, v);
    }
}

struct Edge{
    int u, v, w;
    bool operator<(const Edge& oth) const{
        return w < oth.w;
    }
};

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W){
    vector<Edge> e;
    rep(i, 0, M){
        e.pb({U[i], V[i], W[i]});
    }
    sort(all(e));
    root = N;
    init(N + M);
    rep(i, 0, M){
        auto [u, v, w] = e[i];
        deg[u]++, deg[v]++;
        if(deg[u] >= 3) dsu_c[u] = true;
        if(deg[v] >= 3) dsu_c[v] = true;
        unite(u, v, w);
    }
    rep(i, 0, N + M){
        if(find(i) == i)
            dfs(i, -1);
    }
    rep(k, 0, MAXK - 1){
        rep(i, 0, N + M){
            if(p[k][i] != -1){
                p[k + 1][i] = p[k][p[k][i]];
            } else{
                p[k + 1][i] = -1;
            }
        }
    }
}

int query(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    per(k, MAXK - 1, 0){
        if(diff >> k & 1){
            u = p[k][u];
        }
    }
    if(u == v && c[u]) return we[u];
    per(k, MAXK - 1, 0){
        if(p[k][u] != -1 && (p[k][u] != p[k][v] || !c[p[k][u]])){
            u = p[k][u], v = p[k][v];
        }
    }
    if(p[0][u] == -1) return -1;
    return we[p[0][u]];
}

int getMinimumFuelCapacity(int X, int Y){
    return query(X, Y);
}

Compilation message (stderr)

swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:78:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   78 |         auto [u, v, w] = e[i];
      |              ^

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