Submission #802849

#	Time	Username	Problem	Language	Result	Execution time	Memory
802849		radaiosm7	Swapping Cities (APIO20_swap)	C++11	0 / 100	2077 ms	5432 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int i, n, m, ans;
int par[100005];
int dep[100005];
pair<int, pair<int, int> > edges[200005];

int find_par(int x) {
  if (par[x] == x) return x;
  par[x] = find_par(par[x]);
  return par[x];
}

bool isSame(int x, int y) {
  return (find_par(x) == find_par(y));
}

void Unite(int x, int y) {
  x = find_par(x);
  y = find_par(y);
  if (x == y) return;
  if (dep[x] < dep[y]) swap(x, y);
  if (dep[x] == dep[y]) ++dep[x];
  par[y] = x;
}

void initDSU() {
  for (int k=0; k < n; ++k) {
    par[k] = k;
    dep[k] = 0;
  }
}

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
  n = N;
  m = M;
  for (i=0; i < m; ++i) edges[i] = make_pair(W[i], make_pair(U[i], V[i]));
  sort(edges, edges+m);
}

int f(int a, int b, int c) {
  initDSU();

  for (int j=0; j < m; ++j) {
    if (edges[j].Y.X == c || edges[j].Y.Y == c) continue;
    Unite(edges[j].Y.X, edges[j].Y.Y);
    if (isSame(a, b)) return edges[j].X;
  }

  return INT_MAX;
}

int getMinimumFuelCapacity(int fx, int fy) {
  ans = INT_MAX;

  for (int med=0; med < n; ++med) {
    if (med == fx || med == fy) continue;
    ans = min(ans, max({f(fx, med, fy), f(fy, fx, med), f(med, fy, fx)}));
    ans = min(ans, max({f(fy, med, fx), f(fx, fy, med), f(med, fx, fy)}));
  }
  
  if (ans == INT_MAX) return -1;
  else return ans;
}

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