Submission #975268

#	Time	Username	Problem	Language	Result	Execution time	Memory
975268		MercubytheFirst	Swapping Cities (APIO20_swap)	C++14	0 / 100	0 ms	344 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; // {to, c}

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

  }
  const 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);
  }

  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;
const int LOG = 20;

void init_lca() {
  int n = dsu.size();
  fa.assign(n, vector<int>(LOG, -1));
  dep.assign(n, -1);
  g.assign(n, vector<int>());
  for(int i = 0; i < n; ++i) {
    if(dsu[i].par == i)
      continue;
    fa[i][0] = (dsu[i].par == i ? -1 : dsu[i].par);

  }
  for(int j = 1; j < LOG; ++j) {
    for(int i = 0; i < n; ++i) {
      fa[i][j] = fa[fa[i][j - 1]][j - 1];
    }
  }
}

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  // cout << "wtf1\n";
  edges.assign(M, Edge());
  for(int i = 0; i < M; ++i) {
    edges[i] = {U[i], V[i], W[i]};
  }
  // cout << "wtf2\n";
  sort(edges.begin(), edges.end());
  for(int i = 0; i < N; ++i) {
    dsu.emplace_back(Node(i));
  }
  // cout << "wtf3\n";
  for(const Edge& e : edges) {
    merge(e.from, e.to, e.c);
  }
  // cout << "wtf4\n";
  // int len = dsu.size();
  // for(int i = 0; i < len; ++i) {
  //   cout << i << " : " << dsu[i].par << ' ' << dsu[i].w << endl;
  // }
}

int getMinimumFuelCapacity(int X, int Y) {
  if(get_root(X) != get_root(Y)) {
    return -1;
  }
  return 37;
}

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