Submission #883730

#	Time	Username	Problem	Language	Result	Execution time	Memory
883730		Dec0Dedd	Swapping Cities (APIO20_swap)	C++14	100 / 100	725 ms	164372 KiB

swap

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 3e5+10;
const int K = 20;
const int INF = 1e9+10;

vector<pii> G[N], add[N];
int n, m, a[N], b[N], dpdwn[N], dpup[N];

vector<pii> ed;

struct dsu {
    vector<int> p;

    void init(int sz) {
        p.resize(sz+10);
        for (int i=0; i<sz+10; ++i) p[i]=i;
    }

    int f(int x) {
        if (p[x] == x) return x;
        return p[x]=f(p[x]);
    }

    void mrg(int x, int y) {
        x=f(x), y=f(y);
        if (x == y) return;
        p[x]=y;
    }
};

dsu d;

int up[K][N], mx[K][N], mxd[K][N], tin[N], tout[N], dwn[N], pvl[N], t;
multiset<int> ms[N];
vector<int> ds[N], wgs[N];

void dfs(int v, int p, int w, int mwo) {
    up[0][v]=p, mx[0][v]=w, mxd[0][v]=mwo, tin[v]=++t;
    for (int j=1; j<K; ++j) up[j][v]=up[j-1][up[j-1][v]];
    for (int j=1; j<K; ++j) mx[j][v]=max(mx[j-1][v], mx[j-1][up[j-1][v]]);
    for (int j=1; j<K; ++j) mxd[j][v]=min(mxd[j-1][v], mxd[j-1][up[j-1][v]]);
    dwn[v]=INF;

    for (auto u : G[v]) {
        if (u.second == p) continue;
        wgs[v].push_back(u.first);
        ms[v].insert(u.first);
    } sort(wgs[v].begin(), wgs[v].end());

    if ((int)wgs[v].size() >= 2) dwn[v]=max(wgs[v][0], wgs[v][1]);

    for (auto u : G[v]) {
        if (u.second == p) continue;
        int k;
        if (wgs[v][0] == u.first) {
            if ((int)wgs[v].size() == 1) k=INF;
            else k=wgs[v][1]; 
        } else k=wgs[v][0];
        dfs(u.second, v, u.first, k);
        if (dwn[u.second] < INF) dwn[v]=min(dwn[v], max(dwn[u.second], u.first));
        ds[v].push_back(max(dwn[u.second], u.first));
    } tout[v]=t++, sort(ds[v].begin(), ds[v].end());
}

void dfs2(int v, int p, int ppk) {
    pvl[v]=ppk;
    if (v != 1) pvl[v]=max(pvl[v], mx[0][v]);

    for (auto u : G[v]) {
        if (u.second == p) continue;
        int tmp=pvl[v];
        if ((int)wgs[v].size() >= 3) {
            if (u.first == wgs[v][0]) tmp=min(tmp, wgs[v][2]); // wgs[1], wgs[2]
            else if (u.first == wgs[v][1]) tmp=min(tmp, wgs[v][2]); // wgs[0], wgs[2]
            else tmp=min(tmp, wgs[v][1]); // wgs[0], wgs[1]
        }

        if (v != 1 && (int)wgs[v].size() >= 2) {
            if (u.first == wgs[v][0]) tmp=min(tmp, max(wgs[v][1], mx[0][v]));
            else tmp=min(tmp, max(wgs[v][0], mx[0][v]));
        }

        if ((int)ds[v].size() >= 2) {
            if (dwn[u.second] == ds[v][0]) tmp=min(tmp, ds[v][1]);
            else tmp=min(tmp, ds[v][0]);
        } dfs2(u.second, v, tmp);
    }
}

void dfs3(int v, int p) {
    dpdwn[v]=INF;
    for (auto u : G[v]) {
        if (u.second == p) continue;
        dfs3(u.second, v);
        dpdwn[v]=min(dpdwn[v], max(dpdwn[u.second], u.first));
    }

    for (auto u : add[v]) dpdwn[v]=min(dpdwn[v], u.first);
}

void dfs4(int v, int p, int px) {
    dpup[v]=px;

    vector<int> dps;
    for (auto u : G[v]) {
        if (u.second == p) continue;
        dps.push_back(max(dpdwn[u.second], u.first));
    } sort(dps.begin(), dps.end());

    for (auto u : add[v]) dpup[v]=min(dpup[v], u.first);
    for (auto u : G[v]) {
        if (u.second == p) continue;
        int tp=dpup[v];
        if ((int)dps.size() >= 2) {
            if (dps[0] == max(dpdwn[u.second], u.first)) tp=min(tp, dps[1]);
            else tp=min(tp, dps[0]);
        } dfs4(u.second, v, max(u.first, tp));
    }
}

bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int lca(int v, int u) {
    if (anc(v, u)) return v;
    if (anc(u, v)) return u;
    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][v], u)) v=up[j][v];
    } return up[0][v];
}

int mwp(int v, int u) {
    int l=lca(v, u);

    int cv=v, cu=u, res=0;
    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cv], u)) {
            res=max(res, mx[j][cv]);
            cv=up[j][cv];
        }
    }

    if (cv != l) res=max(res, mx[0][cv]);

    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cu], v)) {
            res=max(res, mx[j][cu]);
            cu=up[j][cu];
        }
    }

    if (cu != l) res=max(res, mx[0][cu]);
    return res;
}

int mwo(int v, int u) {
    int l=lca(v, u);

    if (v == l) swap(v, u);
    int cv=v, cu=u, res=dwn[v];
    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cv], u)) {
            res=min(res, mxd[j][cv]);
            cv=up[j][cv];
        }
    }

    for (int j=K-1; j>=0; --j) {
        if (!anc(up[j][cu], v)) {
            res=min(res, mxd[j][cu]);
            cu=up[j][cu];
        }
    }

    if (u == l) {
        res=min(res, dwn[v]);

        int tpw=mx[0][cv];

        int k;
        if (u == 1) k=INF;
        else k=mx[0][u];

        if (u != 1) res=min(res, max(k, pvl[u]));

        //cout<<"HERE "<<u<<" || "<<k<<" || "<<pvl[u]<<"\n";

        if ((int)wgs[u].size() >= 3) {
            if (tpw == wgs[u][0]) res=min(res, wgs[u][2]); // wgs[1], wgs[2]
            else if (tpw == wgs[u][1]) res=min(res, wgs[u][2]); // wgs[0], wgs[2]
            else res=min(res, wgs[u][1]); // wgs[0], wgs[1]
        }

        if (k < INF && (int)wgs[u].size() >= 2) {
            if (tpw == wgs[u][0]) res=min(res, max(wgs[u][1], k)); // wgs[1], k
            else res=min(res, max(wgs[u][0], k));
        }

        //cout<<"size "<<ds[u].size()<<" ==> "<<ds[u][0]<<", "<<ds[u][1]<<"\n";
        if ((int)ds[u].size() >= 2) {
            if (dwn[cv] == ds[u][0]) res=min(res, ds[u][1]);
            else res=min(res, ds[u][0]);
        }
    } else {
        res=min(res, dwn[u]);
        if (l != 1) res=min(res, mx[0][l]);
        res=min({res, dwn[v], dwn[u]});

        int au=-1, av=-1;
        av=mx[0][cv], ms[l].erase(ms[l].find(mx[0][cv]));
        au=mx[0][cu], ms[l].erase(ms[l].find(mx[0][cu]));
        if (!ms[l].empty()) res=min(res, *ms[l].begin());
        ms[l].insert(au), ms[l].insert(av);
    } return res;
}

bool ok=false;
void init(int _n, int _m, vector<int> x, vector<int> y, vector<int> w) {
    n=_n, m=_m;
    for (int i=0; i<m; ++i) {
        ++x[i], ++y[i];
        a[i+1]=x[i], b[i+1]=y[i];
        ed.push_back({w[i], i+1});
    } sort(ed.begin(), ed.end());

    d.init(n+10);
    for (auto u : ed) {
        if (d.f(a[u.second]) == d.f(b[u.second])) {
            add[a[u.second]].push_back({u.first, b[u.second]});
            add[b[u.second]].push_back({u.first, a[u.second]});
        } else {
            d.mrg(a[u.second], b[u.second]);
            G[a[u.second]].push_back({u.first, b[u.second]});
            G[b[u.second]].push_back({u.first, a[u.second]});
        }
    } dfs(1, 1, 0, INF);
    dfs2(1, 1, INF);
    dfs3(1, 1);
    dfs4(1, 1, INF);
}

int getMinimumFuelCapacity(int x, int y) {
    ++x, ++y;
    if (d.f(x) != d.f(y)) return -1;
    int val=max(mwp(x, y), min({mwo(x, y), dpup[x], dpup[y], dpdwn[x], dpdwn[y]}));
    if (val >= INF) return -1;
    return val;
}

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