Submission #1203299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203299		temporary1	Swapping Cities (APIO20_swap)	C++17	100 / 100	101 ms	15024 KiB

swap

#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }

const int MOD = 1e9+7; // 998244353;

vctr<pii> adj[100005];
int d[100005];
int pw[100005];
int pa[100005];
int deg[100005];
int nxt[100005];

struct DSU {
  void init(int n) {
      fill(pa+1,pa+n+1,-1);
      fill(nxt+1,nxt+n+1,2e9);
  }

  int root(int x) {
    return pa[x] < 0 ? x : root(pa[x]);
  }

  int unite(int x, int y, int w) {
    int px = root(x);
    int py = root(y);
    if (pa[px] > pa[py])swap(px,py),swap(x,y);
    if (++deg[x] > 2) {
      amin(nxt[px],w);
    }
    if (++deg[y] > 2) {
      amin(nxt[px],w);
    }
    if (px == py) {
      amin(nxt[px],w);
      return -1;
    }
    pa[px] += pa[py];
    pa[py] = px;
    adj[px].eb(py,w);
      amin(nxt[px],max(w,nxt[py]));
    pw[py] = w;
    return px;
  }
} dsu;

void dfs(int node, int fa) {
  d[node] = d[fa]+1;
  for (auto [it,w] : adj[node]) {
    if (it == fa)continue;
    // cout << node << "->" << it << '\n';
    amin(nxt[it],max(w,nxt[node]));
    dfs(it,node);
  }
  return;
}

void init(int n, int m, vctr<int> U, vctr<int> V, vctr<int> W) {
  vctr<tiii> edges;
  for (int i = 0; i < m; ++i) {
    edges.eb(W[i],U[i],V[i]);
  }
  sort(all(edges));
  dsu.init(n);
  for (auto [w,u,v] : edges) {
    ++u; ++v;
    // brick(w);brick(u);dbg(v);
    dsu.unite(u,v,w);
  }
  dfs(dsu.root(1),0);
  return;
}

int getMinimumFuelCapacity(int x, int y) {
  ++x; ++y;
  int xi = x, yi = y;
  if (d[xi] > d[yi])swap(xi,yi), swap(x,y);
  int prv = 0;
  while (d[xi] < d[yi])prv = yi, yi = pa[yi];
  if (xi == yi) {
    int ans = max(nxt[xi],pw[prv]);
    if (ans == (int)2e9)ans = -1;
    return ans;
  }
  while (pa[xi] != pa[yi])xi = pa[xi], yi = pa[yi];
  int ans = max(nxt[pa[xi]],max(pw[xi],pw[yi]));  
  if (ans == (int)2e9)ans = -1;
  return ans;
}

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