Submission #975283

#	Time	Username	Problem	Language	Result	Execution time	Memory
975283		MercubytheFirst	Swapping Cities (APIO20_swap)	C++14	100 / 100	390 ms	55300 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e9 + 37;
vector<vector<int> > g;

struct Edge
{
  int from, to, c;
  Edge() { }
  Edge(int u, int v, int w) : from(u), to(v), c(w) { 

  }
  bool operator<(const Edge& other) const {
    return c < other.c;
  }
};

struct Node
{
  bool is_line = true;
  array<int, 2> endpoints;
  int par, size, w;
  Node(int u) : endpoints({u, u}), par(u), size(1), w(inf) {
  
  }
};

vector<Node> dsu;
vector<Edge> edges;
int idx = -1;
int get_root(int v) { // currently slow
  return (dsu[v].par == v ? v : dsu[v].par = get_root(dsu[v].par));
}

void merge(int u, int v, int c) {
  int paru = get_root(u), parv = get_root(v);
  if(paru == parv) {
    dsu[paru].is_line = false;
    dsu[paru].w = min(dsu[paru].w, c);
    return;
  }
  if(dsu[paru].size > dsu[parv].size) {
    swap(u, v);
    swap(paru, parv);
  }
  int cur_node = dsu.size();
  dsu.emplace_back(Node(cur_node));
  if(find(dsu[paru].endpoints.begin(), dsu[paru].endpoints.end(), u) != dsu[paru].endpoints.end() and 
     find(dsu[parv].endpoints.begin(), dsu[parv].endpoints.end(), v) != dsu[parv].endpoints.end()) {
    
    dsu[cur_node].endpoints = {dsu[paru].endpoints[dsu[paru].endpoints[0] == u], dsu[parv].endpoints[dsu[parv].endpoints[0] == v]};
  }
  else {
    dsu[cur_node].endpoints = {-1, -1};
    dsu[cur_node].is_line = false;
    dsu[cur_node].w = min(dsu[cur_node].w, c);
  }
  g.emplace_back();
  g[cur_node].push_back(paru);
  g[cur_node].push_back(parv);
  dsu[paru].par = dsu[parv].par = cur_node;
  dsu[cur_node].size = dsu[paru].size + dsu[parv].size;
}

vector<vector<int> > fa;
vector<int> dep, closest_anc;
const int LOG = 20;

void depth_dfs(int v, int cur_close) {
  if(dsu[v].w != inf)
    cur_close = v;
  closest_anc[v] = cur_close;
  for(int to : g[v]) {
    dep[to] = dep[v] + 1;
    fa[to][0] = v;
    depth_dfs(to, cur_close);
  }
}

void init_lca(void) {
  int n = dsu.size();
  closest_anc.assign(n, -1);
  fa.assign(n, vector<int>(LOG, -1));
  dep.assign(n, -1);
  for(int i = 0; i < n; ++i) {
    if(dep[i] == -1) {
      int v = get_root(i);
      dep[v] = 0;
      depth_dfs(v, -1);
    }
  }
  for(int jump = 1; jump < LOG; ++jump) {
    for(int i = 0; i < n; ++i) {
      fa[i][jump] = (fa[i][jump - 1] == -1 ? -1 : fa[fa[i][jump - 1]][jump - 1]);
    }
  }
  // for(int i = 0; i < n; ++i) {
  //   cout << i << " : ";
  //   for(int j = 0; j < 3; ++j)
  //     cout << fa[i][j] << ' ';
  //   cout << endl;
  // }
}


int lca(int u, int v) {
  if(dep[u] < dep[v]) {
    swap(u, v);
  }
  int diff = dep[u] - dep[v];
  // cout << u << ' ' << v << " Diff : " << diff << endl;
  for(int jump = 0; jump < LOG; ++jump) {
    if((1 << jump) & diff)
      u = fa[u][jump];
  }
  assert(u != v);
  assert(u != -1);
  for(int jump = LOG - 1; jump >= 0; --jump) {
    if(u == -1 or v == -1) {
      // if(u == -1)
      //   cout << "u";
      // if(v == -1)
      //   cout << "v";
      // cout << endl;
      assert(false);
    }
    if(fa[u][jump] != fa[v][jump]) {
      u = fa[u][jump];
      v = fa[v][jump];
      assert(u != -1 and v != -1);
    }
  }
  assert(u != v);
  return closest_anc[fa[u][0]];
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  g.assign(N, vector<int>());
  edges.assign(M, Edge());
  for(int i = 0; i < M; ++i) {
    edges[i] = {U[i], V[i], W[i]};
  }
  sort(edges.begin(), edges.end());
  for(int i = 0; i < N; ++i) {
    dsu.emplace_back(Node(i));
  }
  for(const Edge& e : edges) {
    merge(e.from, e.to, e.c);
  }
  init_lca();
}

int getMinimumFuelCapacity(int X, int Y) {
  if(get_root(X) != get_root(Y)) {
    return -1;
  }
  int anc = lca(X, Y);
  if(anc == -1) {
    return -1;
  }
  assert(dsu[anc].w != inf);
  return dsu[anc].w;
}

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