Submission #576552

#	Time	Username	Problem	Language	Result	Execution time	Memory
576552		radal	Swapping Cities (APIO20_swap)	C++17	13 / 100	646 ms	69860 KiB

swap

#include <bits/stdc++.h>
#include "swap.h"
#pragma GCC target("sse,sse2,sse4,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
constexpr int N = 1e5+20,mod = 998244353,inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
//    if (a+b < 0) return a+b+mod;
    return a+b;
}
 
inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}
vector<pll> adj[N];
vector<int> be[N],fr[N];
vector<pair<int,pll> > e;
int n,m,maxdeg;
int pr[N],par[N][20],h[N],mx[N][20],mi[N][20][2],bmi[N];
bool good[N];
multiset<int> st[N];
void dfs2(int v,int p){
    for (pll u : adj[v]){
        if (u.X == p) continue;
        dfs2(u.X,v);
        if(st[u.X].size() > st[v].size()) swap(st[v],st[u.X]);
        while (!st[u.X].empty()){
            int x = *(st[u.X].begin());
            st[v].insert(x);
            st[u.X].erase(st[u.X].begin());
        }
    }
    for (int x : be[v]) st[v].insert(x);
    for (int x : fr[v]) st[v].erase(st[v].find(x));
    if (st[v].empty()) return;
    int g = *(st[v].begin());
    bmi[v] = g;
    if (g < mi[v][0][0]){
        mi[v][0][1] = mi[v][0][0];
        mi[v][0][0] = g;
        return;
    }
    if (g < mi[v][0][1]) mi[v][0][1] = g;
}
void dfs(int v,int p){
    par[v][0] = p;
    int g[3];
    rep(i,0,3) g[i] = inf;
    for (auto u : adj[v]){
        int w = u.Y;
        if (u.X == p) continue;
        h[u.X] = h[v]+1;
        mx[u.X][0] = w;
        dfs(u.X,v);
        if (w < g[0]){
            g[2] = g[1];
            g[1] = g[0];
            g[0] = w;
            continue;
        }
        if (w < g[1]){
            g[2] = g[1];
            g[1] = w;
            continue;
        }
        if (w < g[2]) g[2] = w;
    }
    for (auto u : adj[v]){
        if (u.X == p) continue;
        int w = u.Y;
        if (g[0] < w){
            mi[u.X][0][0] = g[0];
            if (g[1] < w) mi[u.X][0][1] = g[1];
            else mi[u.X][0][1] = g[2];
        }
        else{
            mi[u.X][0][0] = g[1];
            mi[u.X][0][1] = g[2];
        }
    }
}

int getpar(int v,int k){
    rep(i,0,20)
        if (k&(1 << i))
             v = par[v][i];
    return v;
}

int lca(int u,int v){
    if (h[u] > h[v]) swap(u,v);
    if (h[v]-h[u]) v = getpar(v,h[v]-h[u]);
    if (u == v) return u;
    repr(i,19,0){
        if (par[v][i] != par[u][i]){
            v = par[v][i];
            u = par[u][i];
        }
    }
    return par[v][0];
}

int calc_mx(int v,int k){
    int ans = 0;
    repr(i,19,0){
        if (k >= (1 << i)){
            ans = max(ans,mx[v][i]);
            v = par[v][i];
            k -= (1 << i);
        }
    }
    return ans;
}
int calc_mi(int v,int k){
    int ans = inf;
    repr(i,19,0){
        if (k >= (1 << i)){
            ans = min(ans,mi[v][i][0]);
            v = par[v][i];
            k -= (1 << i);
        }
    }
    return ans;
}
int getpr(int v){
    if (pr[v] == v) return v;
    return pr[v] = getpr(pr[v]);
}

void init (int nn,int mm,vector<int> U,vector<int> V,vector<int> W){
    memset(mi,63,sizeof mi);
    memset(bmi,63,sizeof bmi);
    n = nn;
    m = mm;
    rep(i,0,n) pr[i] = i;
    rep(i,0,m){
        U[i]++;
        V[i]++;
        e.pb({W[i],{U[i],V[i]}});
    }
    sort(all(e));
    rep(i,0,m){
        int x = e[i].Y.X,y = e[i].Y.Y;
        if (getpr(x) != getpr(y)){
            good[i] = 1;
            pr[pr[x]] = pr[y];
            adj[x].pb({y,e[i].X});
            adj[y].pb({x,e[i].X});
        }
    }
    if (m == n-1){
        rep(i,1,n+1) maxdeg = max(maxdeg,(int)adj[i].size());
    }
    dfs(1,0);
    rep(j,1,20){
        rep(i,1,n+1){
            par[i][j] = par[par[i][j-1]][j-1];
            mx[i][j] = max(mx[i][j-1],mx[par[i][j-1]][j-1]);
        }
    }
    rep(i,0,m){
        if (good[i]) continue;
        int u = e[i].Y.X,v = e[i].Y.Y,w = e[i].X;
        if (h[u] > h[v]) swap(u,v);
        int g = lca(u,v);
        if (u == g){
            fr[u].pb(w);
            be[v].pb(w);
            continue;
        }
        be[v].pb(w);
        be[u].pb(w);
        fr[g].pb(w);
        fr[g].pb(w);
    }
    dfs2(1,0);
    rep(j,1,20){
        rep(i,1,n+1){
            int x0 = mi[par[i][j-1]][j-1][0],x1 = mi[par[i][j-1]][j-1][1];
            rep(k,0,2) mi[i][j][k] = mi[i][j-1][k];
            if (x0 < mi[i][j][0]){
                mi[i][j][1] = min(x1,mi[i][j][0]);
                mi[i][j][0] = x0;
                continue;
            }
            if (x0 < mi[i][j][1])
                mi[i][j][1] = x0;
        }
    }
    debug("end");
}
int getMinimumFuelCapacity(int u, int v){
    u++;
    v++;
    if (m == n-1 && maxdeg == 2) return -1;
    if (h[u] > h[v]) swap(u,v);
    int w = lca(u,v);
    if (u == w){
        int ans = calc_mi(v,h[v]-h[u]-1);
        int x = getpar(v,h[v]-h[u]-1);
        ans = min(ans,bmi[x]);
        if (ans >= inf && adj[u].size() <= 2) return -1;
        if (ans >= inf){
            if (u == 1 || mx[u][0] >= mi[x][0][1]) ans = max(mi[x][0][1],calc_mx(v,h[v]-h[u]));
            else ans = max({mx[u][0],mi[x][0][0],calc_mx(v,h[v]-h[u])});
            return ans;
        }
        int mas = calc_mx(v,h[v]-h[u]);
        if (adj[u].size() <= 2) return max(mas,ans);
        ans = min(ans,mi[x][0][1]);
        if (u != 1) ans = min(ans,max(mx[u][0],mi[x][0][0]));
        return max(ans,mas);
    }
    else{
        int x = getpar(v,h[v]-h[w]-1),y = getpar(u,h[u]-h[w]-1);
        int ans = min(calc_mi(v,h[v]-h[w]-1),calc_mi(u,h[u]-h[w]-1));
        ans = min({ans,bmi[x],bmi[y]});
        if (w != 1) ans = min(ans,mx[w][0]);
        if (mi[x][0][0] != mx[y][0]) ans = min(ans,mi[x][0][0]);
        else ans = min(ans,mi[x][0][1]);
        if (ans >= inf) return -1;
        int mas = max(calc_mx(v,h[v]-h[w]),calc_mx(u,h[u]-h[w]));
        return max(ans,mas);
    }
}

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