| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 576550 | radal | Swapping Cities (APIO20_swap) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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,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);
}
}