Submission #975764

#	Time	Username	Problem	Language	Result	Execution time	Memory
975764		OAleksa	Swapping Cities (APIO20_swap)	C++14	37 / 100	2049 ms	13508 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 69;
vector<tuple<int, int, int>> edges;
int n, m, p[N], sz[N], dg, deg[N];
int root(int v) {
  if (p[v] == v)
    return v;
  return p[v] = root(p[v]);
}
void init(int _n, int _m, vector<int> u, vector<int> v, vector<int> w) {
  n = _n;
  m = _m;
  for (int i = 0;i < m;i++) {
    edges.push_back({w[i], u[i], v[i]});
    deg[u[i]]++;
    deg[v[i]]++;
  }
}

int getMinimumFuelCapacity(int x, int y) {
  int ans = -1;
  int l = 1, r = 1e9;
  auto check = [&](int mid) {
    for (int i = 0;i < n;i++) {
      p[i] = i;
      sz[i] = 1;
      deg[i] = 0;
    }
    for (int i = 0;i < m;i++) {
      int a, b, c;
      tie(c, a, b) = edges[i];
      if (c > mid)
        continue;
      deg[a]++;
      deg[b]++;
      int t = root(a);
      int tt = root(b);
      if (t != tt) {
        if (sz[t] < sz[tt])
          swap(t, tt);
        sz[t] += sz[tt];
        p[tt] = t;
      }
    }
    if (root(x) != root(y))
      return false;
    bool ok = 0, all = 1;
    for (int i = 0;i < n;i++) {
      if (root(i) == root(x)) {
        ok |= (deg[i] > 2);
        all &= (deg[i] == 2);
      }
    }
    return ok || all;
  };
  while (l <= r) {
    int mid = (l + r) / 2;
    if (check(mid)) {
      ans = mid;
      r = mid - 1;
    }
    else
      l = mid + 1;
  }
  return ans;
}
/*
5 6
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
3
1 2
2 4
0 1

3 2
0 1 5
0 2 5
1
1 2

*/

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