Submission #802829

#	Time	Username	Problem	Language	Result	Execution time	Memory
802829		radaiosm7	Swapping Cities (APIO20_swap)	C++11	0 / 100	2054 ms	11488 KiB

swap

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

int find_par(int x) {
  if (par[x] == x) return x;
  else return par[x] = find_par(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 i=0; i < n; ++i) {
    par[i] = i;
    dep[i] = 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) {
    adj[U[i]].push_back(make_pair(V[i], W[i]));
    adj[V[i]].push_back(make_pair(U[i], W[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 (i=0; i < n; ++i) {
    if (i == fx || i == fy) continue;
    ans = min(ans, max({f(fx, i, fy), f(fy, fx, i), f(i, fy, fx)}));
    ans = min(ans, max({f(fy, i, fx), f(fx, fy, i), f(i, 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