Submission #869495

#	Time	Username	Problem	Language	Result	Execution time	Memory
869495		tch1cherin	Swapping Cities (APIO20_swap)	C++17	100 / 100	519 ms	69056 KiB

swap

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

struct merging_dsu {
  vector<int> parent, cnt_v, cnt_e, deg, max_deg, T;
  vector<vector<int>> comp;

  merging_dsu(int size) : parent(size), cnt_v(size, 1), cnt_e(size), deg(size), max_deg(size), T(size, INT_MAX), comp(size) {
    iota(parent.begin(), parent.end(), 0);
    for (int i = 0; i < size; i++) {
      comp[i] = {i};
    }
  }

  int get(int u) {
    return parent[u] == u ? u : (parent[u] = get(parent[u]));
  }

  void unite(int u, int v, int w) {
    int new_val = max(++deg[u], ++deg[v]);
    u = get(u), v = get(v);
    if (u != v) {
      if (cnt_v[u] < cnt_v[v]) {
        swap(u, v);
      }
      parent[v] = u;
      cnt_v[u] += cnt_v[v];
      cnt_e[u] += cnt_e[v];
      max_deg[u] = max(max_deg[u], max_deg[v]);
      for (int x : comp[v]) {
        comp[u].push_back(x);
      }
    }
    max_deg[u] = max(max_deg[u], new_val);
    cnt_e[u]++;
    if (cnt_e[u] >= cnt_v[u] || max_deg[u] > 2) {
      for (int x : comp[u]) {
        T[x] = w;
      }
      comp[u] = vector<int>();
    }
  }
};

struct dsu {
  vector<int> parent, rank;

  dsu(int size) : parent(size), rank(size, 1) {
    iota(parent.begin(), parent.end(), 0);
  }

  int get(int u) {
    return parent[u] == u ? u : (parent[u] = get(parent[u]));
  }

  bool unite(int u, int v) {
    u = get(u), v = get(v);
    if (u != v) {
      if (rank[u] < rank[v]) {
        swap(u, v);
      }
      parent[v] = u;
      rank[u] += rank[v];
      return true;
    }
    return false;
  }
};

const int MAX_L = 20;

struct binary_lifting {
  vector<vector<array<int, 2>>> graph;
  vector<vector<int>> up, dp;
  vector<int> depth;

  binary_lifting() {}

  binary_lifting(vector<vector<array<int, 2>>> _graph) : graph(_graph) {
    int N = (int)graph.size();
    depth = vector<int>(N);
    up = vector<vector<int>>(N, vector<int>(MAX_L));
    dp = vector<vector<int>>(N, vector<int>(MAX_L, INT_MIN));
    DFS(0, 0);
  }

  void DFS(int u, int p) {
    up[u][0] = p;
    for (int i = 1; i < MAX_L; i++) {
      up[u][i] = up[up[u][i - 1]][i - 1];
      dp[u][i] = max(dp[u][i - 1], dp[up[u][i - 1]][i - 1]);
    }
    for (auto [v, w] : graph[u]) {
      if (v != p) {
        depth[v] = depth[u] + 1;
        dp[v][0] = w;
        DFS(v, u);
      }
    }
  }

  int query(int u, int v) {
    if (depth[u] < depth[v]) {
      swap(u, v);
    }
    int ans = INT_MIN;
    for (int i = MAX_L - 1; i >= 0; i--) {
      if (depth[u] - (1 << i) >= depth[v]) {
        ans = max(ans, dp[u][i]);
        u = up[u][i];
      }
    }
    if (u == v) {
      return ans;
    }
    for (int i = MAX_L - 1; i >= 0; i--) {
      if (up[u][i] != up[v][i]) {
        ans = max({ans, dp[u][i], dp[v][i]});
        u = up[u][i];
        v = up[v][i];
      }
    }
    return max({ans, dp[u][0], dp[v][0]});
  }
};

binary_lifting BL;
vector<int> T;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  vector<vector<array<int, 2>>> graph(N);
  vector<array<int, 3>> edges;
  for (int i = 0; i < M; i++) {
    edges.push_back({W[i], U[i], V[i]});
  }
  sort(edges.begin(), edges.end());
  dsu sets(N);
  merging_dsu D(N);
  for (auto [W, U, V] : edges) {
    D.unite(U, V, W);
    if (sets.unite(U, V)) {
      graph[U].push_back({V, W});
      graph[V].push_back({U, W});
    }
  }
  T = D.T;
  BL = binary_lifting(graph);
}

int getMinimumFuelCapacity(int X, int Y) {
  int value = max(T[X], BL.query(X, Y));
  return value == INT_MAX ? -1 : value;
}

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