| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1069231 | TVSown | 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.
///*** Sown_Vipro ***///
/// ->TUYEN QUOC GIA<- ///
#include "swap.h"
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define F first
#define S second
#define pb push_back
#define pi pair<long long, int>
#define pii pair<int, pair<int, int> >
#define all(a) a.begin(), a.end()
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define REP(i, a, b) for(int i = a; i >= b; --i)
#define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
#define out(name) if(fopen(name, "w")) freopen(name, "w", stdout);
#define szz(s) int(s.size())
const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7;
int n, nn, m;
long long p[N], b[N], check[N], nxt[25][N], h[N];
vector<long long> adj[N];
struct edge{
long long u, v, w;
} e[N];
bool cmp(edge a, edge b){
return a.w < b.w;
}
long long Find(long long u){
if(u == p[u]) return u;
return p[u] = Find(p[u]);
}
void Union(long long u, long long v){
++b[u]; ++b[v];
long long uu = u, vv = v;
++n;
p[n] = n;
u = Find(u); v = Find(v);
if(u == v){
p[u] = n;
adj[u].pb(n);
adj[n].pb(u);
check[n] = 1;
}else{
p[u] = n; p[v] = n;
check[n] = (check[u] || check[v] || b[uu] > 2 || b[vv] > 2);
adj[u].pb(n);
adj[n].pb(u);
adj[v].pb(n);
adj[n].pb(v);
}
}
void dfs(long long u){
for(long long v : adj[u]){
if(v == nxt[0][u]) continue;
h[v] = h[u] + 1;
nxt[0][v] = u;
dfs(v);
}
}
long long lca(long long u, long long v){
if(h[u] < h[v]) swap(u, v);
REP(k, 20, 0){
long long pu = nxt[k][u];
if(h[pu] >= h[v]){
u = pu;
}
}
if(u == v) return u;
REP(k, 20, 0){
long long pu = nxt[k][u], pv = nxt[k][v];
if(pu != pv){
u = pu; v = pv;
}
}
return nxt[0][u];
}
long long lift(long long u, long long mid){
REP(k, 20, 0){
if((1 << k) <= mid){
u = nxt[k][u];
mid -= (1 << k);
}
}
return u;
}
long long getMinimumFuelCapacity(long long u, long long v){
long long p = lca(u, v);
long long l = 0, r = h[p];
while(l <= r){
long long mid = (l + r) / 2;
if(check[lift(p, mid)]) r = mid - 1;
else l = mid + 1;
}
if(l > h[p]) return -1;
return e[lift(p, l) - nn].w;
}
void init(long long N, long long M, std::vector<long long> U, std::vector<long long> V, std::vector<long long> W){
n = N; m = M;
nn = N;
FOR(i, 1, m){
e[i] = {U[i - 1], V[i - 1], W[i - 1]};
}
sort(e + 1, e + 1 + m, cmp);
FOR(u, 0, n) p[u] = u;
FOR(i, 1, m){
long long u = e[i].u, v = e[i].v;
Union(u, v);
}
h[n] = 1;
dfs(n);
FOR(k, 1, 20){
FOR(u, 0, n){
nxt[k][u] = nxt[k - 1][nxt[k - 1][u]];
}
}
}