Submission #414346

#	Time	Username	Problem	Language	Result	Execution time	Memory
414346		prvocislo	Swapping Cities (APIO20_swap)	C++17	37 / 100	2058 ms	12084 KiB

swap

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

class dsu
{
public:
  vector<int> p, s, ok; // ok - je tento komponent cyklus alebo obsahuje rozvetvenie?
  int root(int x) { return x == p[x] ? x : p[x] = root(p[x]); }
  void merge(int a, int b)
  {
    a = root(a), b = root(b);
    if (a == b) return ok[a] = true, void(); // cyklus
    if (s[a] < s[b]) swap(a, b);
    p[b] = a; s[a] += s[b];
    ok[a] |= ok[b]; 
  }
  void good(int u) { ok[root(u)] = true; }
  dsu(int n): p(vector<int>(n)), s(vector<int>(n, 1)), ok(vector<int>(n, false))
  {
    for (int i =0;i<n;i++) p[i] = i;
  }
};
struct edge { int u, v, w; };
bool cmp(edge a, edge b) { return a.w < b.w; }
int n, m;
vector<edge> e;
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n = N, m = M;
  for (int i = 0; i < m;i++) e.push_back({U[i], V[i], W[i]}); 
  sort(e.begin(), e.end(), cmp);
}
int getMinimumFuelCapacity(int x, int y) {
  dsu c(n);
  vector<int> deg(n, 0);
  for (int i = 0; i < m; i++)
  {
    c.merge(e[i].u, e[i].v);
    deg[e[i].u]++, deg[e[i].v]++;
    if (deg[e[i].u] >= 3) c.good(e[i].u);
    if (deg[e[i].v] >= 3) c.good(e[i].v);
    if (c.root(x) == c.root(y) && c.ok[c.root(x)]) return e[i].w;
  }
  return -1;
}

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