Submission #1305800

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305800		peteza	Swapping Cities (APIO20_swap)	C++20	100 / 100	393 ms	14916 KiB

swap

//baby do u kno what u wanna hearrrr
#include "swap.h"
#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> par[100005];
int h[100005];
int valid[100005];
int deg[100005];

int fpar(int x, int ct) {
  //find parent with time <= ct
  auto it = --upper_bound(par[x].begin(), par[x].end(), make_pair(ct, INT_MAX));
  //cout << x;
  return (it->second == x ? x : fpar(it->second, ct));
}

vector<int> wws;

void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  for(int i=0;i<N;i++) {
    valid[i] = INT_MAX;
    par[i].clear(); h[i] = 0;
    par[i].emplace_back(0, i);
    //time 0 === parent = i
    deg[i] = 0;
  }
  wws = W; wws.push_back(0);
  sort(wws.begin(), wws.end());
  vector<int> edgord(M); iota(edgord.begin(), edgord.end(), 0);
  sort(edgord.begin(), edgord.end(), [&](int a, int b) {
    return W[a] < W[b];
  });
  for(int i=0;i<M;i++) {
    //at time i+1, add the i-th edge
    int a = fpar(U[edgord[i]], M), b = fpar(V[edgord[i]], M);
    if(a == b) {
      //formed cycle!!
      valid[a] = min(valid[a], i+1);
    } else {
      deg[U[edgord[i]]]++; deg[V[edgord[i]]]++;
      int na = a;
      if(h[a] > h[b]) {
        par[b].emplace_back(i+1, a);
      } else {
        par[a].emplace_back(i+1, b);
        na = b;
        h[b]++;
      }
      
      if(min(valid[a], valid[b]) < INT_MAX) valid[na] = min(valid[na], i+1);
      if(max(deg[U[edgord[i]]], deg[V[edgord[i]]]) > 2) valid[na] = min(valid[na], i+1);
    }
  }
}

int getMinimumFuelCapacity(int X, int Y) {
  //bsearch for first time
  int l=0, r=wws.size(), mid;
  while(l < r) {
    mid = (l+r) >> 1;
    int a = fpar(X, mid), b = fpar(Y, mid);
    if(a != b || mid < valid[a]) l = mid+1;
    else r = mid;
  }
  //cout << l << '\n';
  return (l>=wws.size()?-1:wws[l]);
}

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