Submission #550998

#	Time	Username	Problem	Language	Result	Execution time	Memory
550998		hoanghq2004	Swapping Cities (APIO20_swap)	C++14	37 / 100	2089 ms	12104 KiB

swap

#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define Submit
#ifdef Submit
#include "swap.h"

#endif // Submit

using namespace __gnu_pbds;
using namespace std;

const int N = 1e5 + 10;

int n;
vector <tuple <int, int, int> > g;
int deg[N];

void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
    n = N;
    for (int i = 0; i < M; ++i)
        g.push_back({W[i], U[i], V[i]});
    sort(g.begin(), g.end());
}

int par[N], sz[N], ok[N];
int Find(int u) {
    return (u == par[u] ? u : par[u] = Find(par[u]));
}

void Union(int u, int v) {
    ++deg[u], ++deg[v];
    int ru = Find(u), rv = Find(v);
    if (ru != rv) {
        if (sz[ru] < sz[rv]) swap(ru, rv);
        par[rv] = ru;
        sz[ru] += rv;
        ok[ru] |= ok[rv];
    } else ok[ru] = 1;
    if (deg[u] > 2 || deg[v] > 2) ok[ru] = 1;
}

int getMinimumFuelCapacity(int X, int Y) {
    for (int i = 0; i < n; ++i) par[i] = i, deg[i] = 0, ok[i] = 0, sz[i] = 1;
    for (auto [w, u, v]: g) {
        Union(u, v);
        if (Find(X) == Find(Y) && ok[Find(X)]) return w;
    }
    return -1;
}


#ifndef Submit

int main() {
  int N, M;
  assert(2 == scanf("%d %d", &N, &M));

  std::vector<int> U(M), V(M), W(M);
  for (int i = 0; i < M; ++i) {
    assert(3 == scanf("%d %d %d", &U[i], &V[i], &W[i]));
  }

  int Q;
  assert(1 == scanf("%d", &Q));

  std::vector<int> X(Q), Y(Q);
  for (int i = 0; i < Q; ++i) {
    assert(2 == scanf("%d %d", &X[i], &Y[i]));
  }

  init(N, M, U, V, W);

  std::vector<int> minimum_fuel_capacities(Q);
  for (int i = 0; i < Q; ++i) {
    minimum_fuel_capacities[i] = getMinimumFuelCapacity(X[i], Y[i]);
  }

  for (int i = 0; i < Q; ++i) {
    printf("%d\n", minimum_fuel_capacities[i]);
  }

  return 0;
}

#endif // Submit

Compilation message (stderr)

swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:47:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     for (auto [w, u, v]: g) {
      |               ^

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