Submission #571188

#	Time	Username	Problem	Language	Result	Execution time	Memory
571188		Vanilla	Swapping Cities (APIO20_swap)	C++17	0 / 100	2077 ms	68888 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 2;
int extra = 2e5 + 1;
const int lg = 25;
vector <int> ad [maxn];
int deg[maxn];
int dad [maxn];
int val [maxn];
vector <bool> line (maxn, 1);
vector <int> cmp[maxn];
vector <int> depth (maxn);
int dg[maxn];
int up[maxn][lg];
bool bad1 = 1, bad2 = 1;
 
void dfs (int u) {
    for (auto v: cmp[u]) {
        depth[v] = depth[u] + 1;
        up[v][0] = u;
        for (int i = 1; i < lg; i++){
            up[v][i] = up[up[v][i-1]][i-1];
        }
        dfs(v);
    }
}
 
int lca (int x, int y) {
    if (depth[x] < depth[y]) {
        swap(x, y);
    }
    int k = depth[x] - depth[y];
    for (int i = 0; i < lg; i++){
        if (k & (1 << i)) {
            x = up[x][i];
        }
    }
    if (x == y) return x;
    for (int i = lg - 1; i >= 0; i--) {
        if (up[x][i] != up[y][i]) {
            x = up[x][i];
            y = up[y][i];
        }
    }
    return up[x][0];
}
 
 
int get_dad (int x) {
  return (dad[x] == x ? x: get_dad(dad[x]));
}
 
void merge (int a, int b) {
  a = get_dad(a);
  b = get_dad(b);
  if (a == b) return;
  if (!line[a]) line[b] = 0;
  dad[a] = b;
  cmp[b].push_back(a);
}
 
void find (int u, vector <int> &nodes) {
  nodes.push_back(u);
  for (int v: cmp[u]) {
    find(v, nodes);
  }
}
 
 
struct edg {
  int x,y,cost;
};
 
bool comp (edg &a, edg &b) {
  return a.cost < b.cost;
}
 
void init(int n, int m, vector<int> u, vector<int> v, vector<int> w) {
  vector <edg> eg;
  for (int i = 0; i < maxn; i++){
    dad[i] = i;
    for (int j = 0; j < lg; j++){
      up[i][j] = maxn - 1;
    }
  }
  for (int i = 0; i < m; i++){
    dg[u[i]]++;
    dg[v[i]]++;
    eg.push_back({u[i], v[i], w[i]});
  }
  for (int i = 0; i < n; i++){
    if (dg[i] > 2) bad1 = 0;
    if (dg[i] != 2) bad2 = 0;
  }
  sort(eg.begin(), eg.end(), comp);
  for (auto &[u,v,cost]: eg) {
    // if (u == 1 && v == 4) break;
    int p1 = get_dad(u);
    int p2 = get_dad(v);
    // cout << u << " " << v << " " << p1 << " " << p2 << " ";
    if (p1 == p2) { 
      if (line[p1]) {
        vector <int> nodes;
        find(p1, nodes);
        int node = ++extra;
        for (int i: nodes) {
          dad[i] = node;
          cmp[node].push_back(i);
        }
        line[p1] = 0;
        val[node] = cost;
      }
    }
    else {
      deg[u]++;
      deg[v]++;
      if (deg[u] >= 3 || deg[v] >= 3) {
        int node = ++extra;
        line[node] = 0;
        merge(p1, node);
        merge(p2, node);
        val[node] = cost;
      }
      else merge(u,v);
    }
  }
  // for (int i = 0; i < 15; i++){
  //   cout << i << " " << val[i] << "\n";
  // }
  // for (int i = 0; i < 15; i++){
  //   cout << i << ": ";
  //   for (int j: cmp[i]) {
  //     cout << j << " ";
  //   }
  //   cout << "\n";
  // }
  // for (int i = 0; i < 15; i++){
  //   cout << i << " " << dad[i] << "\n";
  // }
  for (int i = maxn - 1; i >= 0; i--){
    if (cmp[i].size()) {
      dfs(i);
      break;
    }
  }
 
}
 
int getMinimumFuelCapacity(int x, int y) {
  if (bad1 || bad2) return -1;
  return val[lca(x,y)];
}

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