Submission #298660

#	Time	Username	Problem	Language	Result	Execution time	Memory
298660		Bruteforceman	Swapping Cities (APIO20_swap)	C++11	100 / 100	766 ms	80632 KiB

swap

#include "bits/stdc++.h"
#include "swap.h"
using namespace std;
const int maxn = 3e5 + 10;
const int logn = 19;
typedef pair <int, int> pii;
vector <int> g[maxn];
int l[maxn], r[maxn], w[maxn];
int n, m;

int par[maxn];
int deg[maxn];
int dad[maxn];
bool good[maxn];
multiset <int> cont[maxn];
int anc[logn + 1][maxn];
int opt[maxn], dep[maxn];

struct dsu {
  int par[maxn];
  void init(int sz) {
    for(int i = 0; i < sz; i++) {
      par[i] = i;
    }
  }
  int root(int x) {
    if(par[x] == x) return par[x];
    return par[x] = root(par[x]);
  }
  void join(int x, int y) {
    x = root(x);
    y = root(y);
    if(x != y) {
      par[x] = y;
    }
  }
} T;

int root(int x) {
  if(par[x] == x) return x;
  return par[x] = root(par[x]);
}
void remove(int x) {
  cont[root(x)].erase(cont[root(x)].find(deg[x]));
}
void add(int x) {
  cont[root(x)].insert(deg[x]);
}
void join(int x, int y) {
  remove(x);
  remove(y);
  deg[x] += 1;
  deg[y] += 1;
  add(x);
  add(y);
  x = root(x);
  y = root(y);
  if(x != y) {
    if(cont[x].size() > cont[y].size()) swap(x, y);
    for(int i : cont[x]) cont[y].insert(i);
    cont[x].clear();
    par[x] = y;
  }
}
bool check(int x, int y) {
  x = root(x);
  y = root(y);
  if(x != y) return false;
  return not (*cont[x].begin() <= 1 && *cont[x].rbegin() <= 2);
}

void dfs(int x) {
  if(good[x]) opt[x] = w[x - n];
  for(int i : g[x]) {
    dep[i] = 1 + dep[x];
    opt[i] = min(opt[i], opt[x]);
    dfs(i);
  }
}
int lca(int x, int y) {
  if(dep[x] > dep[y]) swap(x, y);
  for(int i = logn; i >= 0; i--) {
    if(dep[y] - (1 << i) >= dep[x]) {
      y = anc[i][y];
    }
  }
  if(x == y) return x;
  for(int i = logn; i >= 0; i--) {
    if(anc[i][x] != anc[i][y]) {
      x = anc[i][x];
      y = anc[i][y];
    }
  }
  return anc[0][x];
}
int getMinimumFuelCapacity(int X, int Y) {
  if(good[lca(X, Y)]) return opt[lca(X, Y)];
  else return opt[X] == INT_MAX ? -1 : opt[X];
}
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  n = N;
  m = M;
  vector <int> ord (m);
  for(int i = 0; i < m; i++) {
    ord[i] = i;
  }
  sort(ord.begin(), ord.end(), [&] (int i, int j) {
      return W[i] < W[j]; } );
  for(int i = 0; i < m; i++) {
    l[i] = U[ord[i]];
    r[i] = V[ord[i]];
    w[i] = W[ord[i]]; 
  }
  T.init(n + m);
  for(int i = 0; i < n; i++) {
    par[i] = i;
    deg[i] = 0;
    cont[i].clear();
    cont[i].insert(0);
  }
  for(int i = 0; i < m; i++) {
    int p = l[i];
    int q = r[i];
    if(root(p) != root(q)) {
      join(p, q);
      dad[T.root(p)] = i + n;
      dad[T.root(q)] = i + n;
      good[i + n] = check(p, q);
      T.join(p, i + n);
      T.join(q, i + n);
    } else {
      join(p, q);
      dad[T.root(p)] = i + n;
      good[i + n] = check(p, q);
      T.join(p, i + n);
    }
  }
  int root = n + m - 1;
  dad[root] = root;
  for(int i = 0; i < n + m; i++) {
    anc[0][i] = dad[i];
    opt[i] = INT_MAX;
    if(i != root) g[dad[i]].push_back(i);
  }
  for(int i = 1; i <= logn; i++) {
    for(int j = 0; j < n + m; j++) {
      anc[i][j] = anc[i - 1][anc[i - 1][j]];
    }
  }
  dep[root] = 0;
  dfs(root);
}

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