Submission #979516

#	Time	Username	Problem	Language	Result	Execution time	Memory
979516		bubble_xd	Swapping Cities (APIO20_swap)	C++17	17 / 100	49 ms	8048 KiB

swap

#include "swap.h"

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

const int nax = 1005;
int N, M;
vector<pair<int, int>> edges; // (W, index)
vector<pair<int, int>> G[nax]; // (V, index of the edge) 
void init(int _N, int _M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  N = _N; M = _M;
  for (int i = 0; i < M; i++) {
    G[U[i]].push_back(make_pair(V[i], i));
    G[V[i]].push_back(make_pair(U[i], i));
    edges.push_back(make_pair(W[i], i));
  }
  sort(edges.begin(), edges.end());
}

int getMinimumFuelCapacity(int X, int Y) {
  vector<bool> vis(N);
  vector<bool> ban(M, true);
  function<void(int, int)> dfs = [&](int u, int f) { 
    // u = current node, f = node that we came from
    // u -> f, f -> u 
    vis[u] = true;
    for (auto v : G[u]) {
      if (v.first == f) continue;
      if (ban[v.second]) continue;

      if (!vis[v.first]) dfs(v.first, u);
    }
  };
  function<bool(int, int)> cycle = [&](int u, int f) { 
    // u = current node, f = node that we came from
    // u -> f, f -> u 
    vis[u] = true;
    for (auto v : G[u]) {
      if (v.first == f) continue;
      if (ban[v.second]) continue;

      if (vis[v.first]) return true;
      // v -> f -> u -> v return true
      if (cycle(v.first, u)) return true;
    }
    return false;
  };
  function<bool()> degree3 = [&]() {
    for (int i = 0; i < N; i++) {
      if (vis[i] == false) continue;
      int deg = 0;
      for (auto & v : G[i]) {
        if (ban[v.second] == false) {
          deg++;
          if (deg >= 3) return true;
        }
      }
    }
    return false;
  };
  for (int i = 0; i < M; i++) {
    vis = vector<bool>(N);
    int w = edges[i].first;
    int id = edges[i].second;
    ban[id] = false;
    dfs(X, -1);
    if (vis[Y] == false) continue;
    if (degree3()) return w;
    vis = vector<bool>(N);
    if (cycle(X, -1)) return w;
  }
  return -1;
}

// #include "grader.cpp"

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