Submission #1166676

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166676		epicci23	Swapping Cities (APIO20_swap)	C++20	100 / 100	948 ms	38140 KiB

swap

#include "bits/stdc++.h"
#include "swap.h"
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()

const int N = 3e5 + 5;
const int LOG = 20;
const int INF = 1e9 + 5;

int lift[N][LOG],dp[N],valid[N],deg[N],ptr;
int par[N],siz[N],ind[N];

inline void add_node(int a,int b,int w){
  lift[a][0] = lift[b][0] = ptr;
  valid[ptr] = max(valid[a], valid[b]);
  dp[ptr] = w;
}

int find(int a){
  if(par[a] == a) return par[a];
  return par[a] = find(par[a]);
}

inline void merge(int a,int b){
  a = find(a), b = find(b);
  if(a == b) return;
  if(siz[a] < siz[b]) swap(a, b);
  siz[a] += siz[b];
  par[b] = a;
}

inline int Find(int c,int w){
 for(int i = LOG - 1; i >= 0; i--) if(dp[lift[c][i]] <= w) c = lift[c][i];
 return c;
}

void init(int _N, int _M, vector<int> U, vector<int> V, vector<int> W) {
  int n = _N, m = _M;
  vector<array<int,3>> edges;

  for(int i=0;i<m;i++){
  	int a = U[i], b = V[i], c = W[i];
  	edges.push_back({c, a, b});
  }

  fill(siz,siz+N,1);
  iota(par,par+N,0);
  iota(ind,ind+N,0);

  ptr = n - 1;

  sort(all(edges));
  for(auto [w, a, b] : edges){
  	int oa = ind[find(a)], ob = ind[find(b)];
  	int ok = (find(a) == find(b));
    merge(a, b);
    ind[find(a)] = ++ptr;
    deg[a]++,deg[b]++;
    add_node(oa,ob,w);
    if(deg[a] >= 3 || deg[b] >= 3 || ok) valid[ptr] = 1;
  }

  lift[ptr][0] = ptr;
  for(int j = 1; j < LOG ; j++) for(int i = 0; i <= ptr; i++) lift[i][j] = lift[lift[i][j-1]][j-1];
}

int getMinimumFuelCapacity(int X, int Y){
    int a = X, b = Y; 
    int l = 0, r = INF;
    while(l < r){
      int mid = (l + r) / 2;
      int ca = Find(a, mid);
      int cb = Find(b, mid);
      if(ca != cb || !valid[ca]) l = mid + 1;
      else r = mid;
    }
    if(l == INF) return -1;
    else return l;
}

/*void _(){
  int n,m;
  vector<array<int,3>> edges;
  cin >> n >> m;
  for(int i=0;i<m;i++){
  	int a,b,c;
  	cin >> a >> b >> c;
  	edges.push_back({c, a, b});
  }

  fill(siz,siz+N,1);
  iota(par,par+N,0);
  iota(ind,ind+N,0);

  ptr = n - 1;

  sort(all(edges));
  for(auto [w, a, b] : edges){
  	int oa = ind[find(a)], ob = ind[find(b)];
  	int ok = (find(a) == find(b));
    merge(a, b);
    ind[find(a)] = ++ptr;
    deg[a]++,deg[b]++;
    add_node(oa,ob,w);
    if(deg[a] >= 3 || deg[b] >= 3 || ok) valid[ptr] = 1;
  }

  lift[ptr][0] = ptr;
  for(int j = 1; j < LOG ; j++) for(int i = 0; i <= ptr; i++) lift[i][j] = lift[lift[i][j-1]][j-1];

  int q; cin >> q;
  while(q--){
  	int a, b; cin >> a >> b;
    int l = 0, r = INF;
    while(l < r){
      int mid = (l + r) / 2;
      int ca = Find(a, mid);
      int cb = Find(b, mid);
      if(ca != cb || !valid[ca]) l = mid + 1;
      else r = mid;
    }
    if(l == INF) cout << -1 << '\n';
    else cout << l << '\n';
  }
}

int32_t main(){
  ios::sync_with_stdio();cin.tie();
  int tc=1;//cin >> tc;
  while(tc--) _();
}*/

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