Submission #979539

#	Time	Username	Problem	Language	Result	Execution time	Memory
979539		bubble_xd	Swapping Cities (APIO20_swap)	C++17	17 / 100	51 ms	8016 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int nax = 1005;
int N, M;
vector<pair<int, pair<int, int>>> edges; // (W, index)
vector<pair<int, int>> G[nax]; // (V, index of the edge) 
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  N = _N; M = _M;
  for (int i = 0; i < M; i++) {
    edges.push_back(make_pair(W[i], make_pair(U[i], V[i])));
    G[U[i]].push_back(make_pair(V[i], i));
    G[V[i]].push_back(make_pair(U[i], i));
  }
  sort(edges.begin(), edges.end());
}

struct dsu {
  vector<int> fa, sz, ok, mx_deg;
  dsu(int n) {
    fa.resize(n + 10);
    iota(fa.begin(), fa.end(), 0);
    ok.assign(n + 10, false);
    mx_deg.assign(n + 10, 0);
    sz.assign(n + 10, 1);
  }
  // representative for each component
  // fa[all the nodes in the component] is the same
  int find(int x) {
    while (x != fa[x]) {
      x = fa[x] = fa[fa[x]];
    }
    return x;
  }
  void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    if (px == py) return;
    if (sz[px] > sz[py]) swap(px, py);
    fa[px] = py;
    sz[py] += sz[px];
    ok[py] = ok[px] || ok[py];
    mx_deg[py] = max(mx_deg[py], mx_deg[px]);
    if (mx_deg[py] >= 3) ok[py] = true;
  }
  bool same(int x, int y) {
    int px = find(x);
    int py = find(y);
    return px == py;
  }
};

int getMinimumFuelCapacity(int X, int Y) {
  dsu D(N);
  vector<int> deg(N);
  for (int i = 0; i < M; i++) {
    int w = edges[i].first;
    int u = edges[i].second.first;
    int v = edges[i].second.second;

    if (D.same(u, v)) D.ok[D.find(u)] = 1;
    deg[u]++; deg[v]++;
    if (deg[u] >= 3) {
      D.mx_deg[D.find(u)] = 3;
      D.ok[D.find(u)] = 1;
    }
    if (deg[v] >= 3) {
      D.mx_deg[D.find(v)] = 3;
      D.ok[D.find(v)] = 1;
    }
    D.merge(u, v);
    if (D.same(X, Y) && D.ok[D.find(X)] == 1) return w;
  }
  return -1;
}

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