Submission #729065

#	Time	Username	Problem	Language	Result	Execution time	Memory
729065		stevancv	Swapping Cities (APIO20_swap)	C++14	6 / 100	526 ms	45156 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 2;
const int inf = 2e9;
struct Dsu {
    int link[N];
    void Init(int n) {
        for (int i = 1; i <= n; i++) link[i] = i;
    }
    int Find(int x) {
        if (x == link[x]) return x;
        return link[x] = Find(link[x]);
    }
    void Unite(int u, int v) {
        u = Find(u); v = Find(v);
        if (u == v) return;
        link[v] = u;
    }
}dsu;
vector<array<int, 3>> g[N];
int par[N][17], mxe[N][17], gmn[N][17], in[N], out[N], dep[N], mnb[N], parval[N], gmnval[N], tsz;
void Dfs(int s, int e) {
    in[s] = ++tsz;
    par[s][0] = e;
    mxe[s][0] = parval[s];
    gmn[s][0] = inf;
    if (g[s].size() >= 3) gmn[s][0] = g[s][2][0];
    gmnval[s] = gmn[s][0];
    for (int i = 1; i < 17; i++) {
        par[s][i] = par[par[s][i - 1]][i - 1];
        mxe[s][i] = max(mxe[s][i - 1], mxe[par[s][i - 1]][i - 1]);
        gmn[s][i] = min(gmn[s][i - 1], gmn[par[s][i - 1]][i - 1]);
    }
    mnb[s] = inf;
    for (auto u : g[s]) {
        if (u[1] != e && u[2] == 1) {
            parval[u[1]] = u[0];
            dep[u[1]] = dep[s] + 1;
            Dfs(u[1], s);
            smin(mnb[s], mnb[u[1]]);
        }
        if (u[2] == 0) {
            smin(mnb[s], u[0]);
        }
    }
    out[s] = tsz;
}
bool Ancestor(int u, int v) {
    return in[u] <= in[v] && out[v] <= out[u];
}
int Lca(int u, int v) {
    if (Ancestor(u, v)) return u;
    if (Ancestor(v, u)) return v;
    for (int i = 16; i >= 0; i--) {
        if (par[u][i] && !Ancestor(par[u][i], v)) u = par[u][i];
    }
    return par[u][0];
}
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
    vector<array<int, 3>> e(m);
    for (int i = 0; i < m; i++) {
        u[i] += 1;
        v[i] += 1;
        e.push_back({w[i], u[i], v[i]});
    }
    dsu.Init(n);
    sort(e.begin(), e.end());
    for (auto u : e) {
        if (dsu.Find(u[1]) == dsu.Find(u[2])) {
            g[u[1]].push_back({u[0], u[2], 0});
            g[u[2]].push_back({u[0], u[1], 0});
        }
        else {
            dsu.Unite(u[1], u[2]);
            g[u[1]].push_back({u[0], u[2], 1});
            g[u[2]].push_back({u[0], u[1], 1});
        }
    }
    for (int i = 0; i < n; i++) {
        sort(g[i].begin(), g[i].end());
    }
    for (int i = 0; i < 17; i++) gmn[0][i] = inf;
    Dfs(1, 0);
}
int GetMxFromPath(int u, int v) {
    int ans = 0;
    int raz = dep[u] - dep[v];
    for (int i = 16; i >= 0; i--) {
        if ((1 << i) & raz) {
            smax(ans, mxe[u][i]);
            u = par[u][i];
        }
    }
    return ans;
}
int GetMnFromPath(int u, int v) {
    int ans = inf;
    int raz = dep[u] - dep[v];
    for (int i = 16; i >= 0; i--) {
        if ((1 << i) & raz) {
            smin(ans, gmn[u][i]);
            u = par[u][i];
        }
    }
    return ans;
}
int Kth(int u, int k) {
    for (int i = 16; i >= 0; i--) {
        if ((1 << i) & k) u = par[u][i];
    }
    return u;
}
int getMinimumFuelCapacity(int x, int y) {
    x += 1; y += 1;
    int lca = Lca(x, y);
    int o = max(GetMxFromPath(x, lca), GetMxFromPath(y, lca));
    if (x != lca && y != lca)smax(o, parval[lca]);
    int xx = par[x][0];
    if (x == lca) xx = Kth(y, dep[y] - dep[x] - 1);
    int yy = par[y][0];
    if (y == lca) yy = Kth(x, dep[x] - dep[y] - 1);
    int ans = inf;
    if (xx != y && yy != x) {
        int oo = min(GetMnFromPath(xx, lca), GetMnFromPath(yy, lca));
        if (x != lca && y != lca) smin(oo, gmnval[lca]);
        smin(ans, max(o, oo));
    }
    smin(ans, max(o, max(mnb[x], mnb[y])));
    if (ans == inf) ans = -1;
    return ans;
}

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