Submission #1226011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226011		Godgift42	Swapping Cities (APIO20_swap)	C++20	37 / 100	2097 ms	10936 KiB

swap

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

vector<int> u;
vector<int> v;
vector<int> w;
vector<pair<int,int>> sm;
int n;
int m;
vector<int> rt;
vector<int> sz;
vector<int> fr;
vector<int> jk;
int find(int u){
  if(rt[u]!=u){
    rt[u]=find(rt[u]);
    if(fr[u] or jk[u]>=3)fr[rt[u]]=1;
  }
  return rt[u];
}

bool unite(int a, int b){
  a=find(a);
  b=find(b);
  if(a==b){
    fr[a]=1;
    return false;
  }
  if(sz[a]>=sz[b]){
    sz[a]+=sz[b];
    if(fr[b])fr[a]=1;
    rt[b]=a;
  }
  else{
    sz[b]+=sz[a];
    if(fr[a])fr[b]=1;
    rt[a]=b;
  }
  return true;
}

bool fk=false;

void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  u=U;
  v=V;
  w=W;
  n=N;
  m=M;
  vector<int> pl(n);
  if(m==n-1){
    fk=true;
    for(int i=0;i<m;i++){
      pl[u[i]]++;
      pl[v[i]]++;
    }
    for(auto i:pl){
      if(i>=3)fk=false;
    }
  }
  for(int i=0;i<M;i++){
    sm.push_back({w[i],i});
  }
  sort(sm.begin(),sm.end());
  fr.resize(n,0);
  sz.resize(n,1);
  jk.resize(n);
  rt.resize(n);
}

int getMinimumFuelCapacity(int X, int Y) {
  if(fk)return -1;
  for(int i=0;i<n;i++){
    rt[i]=i;
    sz[i]=1;
    jk[i]=0;
    fr[i]=0;
  }
  int ans=0;
  
  for(int i=0;i<m;i++){
    jk[u[sm[i].second]]++;
    jk[v[sm[i].second]]++;
    if(jk[u[sm[i].second]]>=3)fr[u[sm[i].second]]=1;
    if(jk[v[sm[i].second]]>=3)fr[v[sm[i].second]]=1;
    bool ko=unite(u[sm[i].second],v[sm[i].second]);
    ans=sm[i].first;
    if(find(X)==find(Y) and fr[find(X)])break;
  }
  return ans;
}

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