Submission #1176732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176732		Mousa_Aboubaker	Swapping Cities (APIO20_swap)	C++20	6 / 100	48 ms	7088 KiB

swap

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

#define vec vector
#define ll long long
#define all(x) x.begin(), x.end()

int const inf = 1e9 + 1;

// let's rephrase the problem statement

// I will give you city i and city j, find a way that have a cycle, and the maximum gas is minimized
// first, find the MST, with this, we have a tree
// after that, we will look for cycles with minimum possible (we can find them on the go in MST algorithm)

// the idea is changed

// when it will be impossible and the answer is -1 for all the cities pairs ?
// when the graph is a path, then the answer is always -1

// otherwise, I can choose one of the following:
// 1 - an edge which isn't on the path from a and b, but on one of its vertices (excpet a and b)
// 2 - choose 2 edges in whether a or b such that none of them is on the path from a to b
// 3 - choose another path is it exists and take it, such that the start is connected with a and the end is connected with b

// let's try to implement this idea

// first, dsu to get time complexity O(alpha)
struct DSU
{
  int n;
  vec<int> par, sz;
  DSU(int _n)
  {
    n = _n;
    sz.assign(n, 1);
    par.resize(n);
    iota(all(par), 0);
  }
  int find(int u)
  {
    return par[u] = (par[u] == u ? u : find(par[u]));
  }
  bool same(int u, int v)
  {
    return find(u) == find(v);
  }
  bool unite(int u, int v)
  {
    u = find(u);
    v = find(v);
    if(u == v)
      return false;
    if(sz[u] > sz[v])
      swap(u, v);
    sz[v] += sz[u];
    par[u] = v;
    return true;
  }
};

int n, m;
vec<int> u, v, w;
int mn = inf;

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W)
{
  n = N, m = M;
  u = U, v = V, w = W;
  // let's solve the first subtask
  if(m > n - 1)
    mn = *max_element(all(w));



  // vec<tuple<int, int, int>> edges;
  // for(int i = 0; i < m; i++)
  //   edges[i] = {w[i], u[i], v[i]};
  // sort(all(edges));
  // DSU dsu(n);
  // // MST code
  // for(auto [wi, ui, vi]: edges)
  // {
  //   int x = dsu.find(ui);
  //   int y = dsu.find(vi);
  //   if(x != y)
  //   {
  //     dsu.unite(x, y);
  //   }
  // }
}

int getMinimumFuelCapacity(int X, int Y)
{
  int x = X, y = Y;
  return (mn == inf ? -1 : mn);
}

/*

- SAMPLES -

01.in
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

01.out
3
10
4

02.in
3 2
0 1 5
0 2 5
1
1 2

02.out
-1

*/

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