Submission #564374

#	Time	Username	Problem	Language	Result	Execution time	Memory
564374		ngpin04	Swapping Cities (APIO20_swap)	C++14	13 / 100	740 ms	58140 KiB

swap

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define bit(x) (1LL << (x))
#define getbit(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  if (a < b) {a = b; return true;} return false;
}
mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());

int rand(int l, int r) {
  return l + rd() % (r - l + 1);
}
const int N = 2e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <int> adj[N];

int max_e[N][20];
int ok_e[N][20];
int ok_v[N][20];
int anc[N][20];
int par[N];
int deg[N];
int fr[N];
int to[N];
int w[N];
int h[N];
int n,m;

bool notmst[N];

int getpar(int u) {
    return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}

bool join(int u, int v) {
    u = getpar(u);
    v = getpar(v);
    if (u == v)
        return false;
    if (par[u] > par[v])
        swap(u, v);
    par[u] += par[v];
    par[v] = u;
    return true;
}

int getlca(int u, int v) {
    if (h[u] > h[v])
        swap(u, v);

    for (int i = 19; i >= 0; i--) 
        if (h[v] - bit(i) >= h[u])
            v = anc[v][i];
    if (u == v)
        return v;

    for (int i = 19; i >= 0; i--) if (anc[u][i] != anc[v][i]) {
        u = anc[u][i];
        v = anc[v][i];
    }
    return anc[v][0];
}

void dfs(int u, int p = -1) {
    anc[u][0] = p;

    for (int i : adj[u]) {
        int v = fr[i] ^ to[i] ^ u;
        if (v == p)
            continue;
        h[v] = h[u] + 1;
        max_e[v][0] = w[i];
        dfs(v, u);
    }
}

void build() {
    vector <int> ind(m, 0);
    iota(ALL(ind), 0);
    sort(ALL(ind), [](int i, int j) {
        return w[i] < w[j];
    });

    for (int i = 0; i < n; i++)
        par[i] = -1;

    for (int i : ind) {
        if (join(fr[i], to[i])) {
            adj[fr[i]].push_back(i);
            adj[to[i]].push_back(i);
        } else 
            notmst[i] = true;
    }

    dfs(0);

    for (int j = 1; j < 20; j++)
    for (int i = 0; i < n; i++) {
        int p = anc[i][j - 1];
        anc[i][j] = (p < 0) ? -1 : (anc[p][j - 1]);
    }

    for (int i = 0; i < n; i++) {
        par[i] = -1;
        ok_v[i][0] = ok_e[i][0] = 2 * oo;
    }
    max_e[0][0] = 2 * oo;

    for (int it : ind) if (notmst[it]) {
        int u = fr[it];
        int v = to[it];
        int p = getlca(u, v);

        for (int i = getpar(u); h[i] > h[p]; i = getpar(i)) {
            ok_e[i][0] = w[it];
            par[i] = anc[i][0];
        }   

        for (int i = getpar(v); h[i] > h[p]; i = getpar(i)) {
            ok_e[i][0] = w[it];
            par[i] = anc[i][0];
        }
    }

    for (int it : ind) {
        int u = fr[it];
        int v = to[it];
        deg[u]++;
        deg[v]++;
        if (deg[u] == 3)
            ok_v[u][0] = w[it];
        if (deg[v] == 3) 
            ok_v[v][0] = w[it];
    }

    for (int j = 1; j < 20; j++) 
    for (int i = 0; i < n; i++) {
        int p = anc[i][j - 1];
        if (p < 0) {
            max_e[i][j] = ok_v[i][j] = ok_e[i][j] = 2 * oo;
        } else {
            ok_v[i][j] = min(ok_v[i][j - 1], ok_v[p][j - 1]);
            ok_e[i][j] = min(ok_e[i][j - 1], ok_e[p][j - 1]);
            max_e[i][j] = max(max_e[i][j - 1], max_e[p][j - 1]);
        }
    }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    m = M;
    for (int i = 0; i < m; i++) {
        fr[i] = U[i];
        to[i] = V[i];
        w[i] = W[i];
    }
    build();
}

int getmax(int u, int p) {
    int res = 0;
    for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
        maxi(res, max_e[u][i]);
        u = anc[u][i];
    }
    return res;
}

int minEdge(int u, int p) {
    int res = 2 * oo;
    for (int i = 19; i >= 0; i--) if (h[u] - bit(i) >= h[p]) {
        mini(res, ok_e[u][i]);
        u = anc[u][i];
    }
    return res;
}

int minVertex(int u, int p) {
    int res = 2 * oo;
    u = anc[u][0];  
    for (int i = 19; i >= 0; i--) if (h[u] - bit(i) > h[p]) {
        mini(res, ok_v[u][i]);
        u = anc[u][i];
    }
    return res;
}

int getMinimumFuelCapacity(int u, int v) {
    if (h[u] > h[v])
        swap(u, v);
    int p = getlca(u, v);
    int res = max(getmax(u, p), getmax(v, p));
    int ed = min(minEdge(u, p), minEdge(v, p));
    int vt = min(minVertex(u, p), minVertex(v, p));
    if (v != p)
        mini(vt, ok_v[p][0]);

    // cerr << u << " " << v << " " << vt << " " << ed << "\n";
    maxi(res, min(vt, ed));
    if (res == 2 * oo)
        res = -1;
    return res;
}

#include "swap.h"
//#include "grader.cpp"

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