제출 #1190358

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190358		emad234	자매 도시 (APIO20_swap)	C++20	100 / 100	346 ms	118252 KiB

swap

#include "swap.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define pii pair<int, int>
const int mxN = 4e5 + 5;
using namespace std;
struct edge{
  int u,v,w;
  friend bool operator<(edge a, edge b){
    return a.w < b.w;
  }
};
vector<vector<pii>>v;
pii st[mxN][32];
bool swp[mxN];
int dsu[mxN],sz[mxN],h[mxN],deg[mxN],id[mxN];
int curid;
void dfs(int u,int p){
  if(u != curid) h[u] = h[p] + 1;
  for(auto x : v[u]) if(x.F != p) dfs(x.F,u);
}
void connect(int x,int y,int z,int val){
  // cout<<x<<' '<<y<<' '<<z<<' '<<val<<'\n';
  v[x].push_back({y,val});
  v[y].push_back({x,val});
  st[y][0] = {x,val};
  if(z != y){
    v[x].push_back({z,val});
    v[z].push_back({x,val});
    st[z][0] = {x,val};
  }
}
int lca(int x,int y){
  int val = 0;
  if(h[x] > h[y]) swap(x,y);
  // cout<<h[x]<<' '<<h[y]<<'\n';
  for(int i = 20;i >= 0;i--){
    int b = st[y][i].F;
    if(h[b] >= h[x]) {
      val = st[y][i].S;
      y = b;
    }
  }
  for(int i = 20;i >= 0;i--){
    int a = st[x][i].F,b = st[y][i].F;
    // cout<<a<<' '<<b<<'\n';
    if(a != b || !(swp[a] || swp[b])){
      val = max({val,st[x][i].S,st[y][i].S});
      x = a;
      y = b;
    }
  }
  val = max(st[x][0].S,st[y][0].S);
  // cout<<st[x][0].F<<'\n';
  return val;
}
int find(int x){
  return (dsu[x] == x ? x : dsu[x] = find(dsu[x]));
}
void merge(int a,int b,int val){
  int fa = find(a),fb = find(b);
  deg[a]++;
  deg[b]++;
  if(sz[a] < sz[b]){
    swap(a,b);
    swap(fa,fb);
  }
  if(fa != fb && sz[fa] == sz[fb]) sz[fa]++;
  dsu[fb] = fa;
  if(swp[fa] || swp[fb] || deg[a] >= 3 || deg[b] >= 3 || fa == fb) swp[fa] = 1;
  connect(++curid,id[fa],id[fb],val);
  id[fa] = curid;
  swp[id[fa]] = swp[fa];
}
vector<edge>edges;
void init(int N, int M, std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  v.resize(2 * (N + M));
  curid = N - 1;
  for(int i = 0;i < M;i++){
    edges.push_back({U[i],V[i],W[i]});
  }
  for(int i = 0;i <= N + M;i++) {
    dsu[i] = i;
    id[i] = i;
  }
  sort(edges.begin(),edges.end());
  for(auto x : edges){
    // cout<<x.u<<' '<<x.v<<' '<<x.w<<'\n';
    merge(x.u,x.v,x.w);
    // int fa = find(x.y);
    // cout<<fa<<' '<<swp[fa]<<'\n';
  }
  st[curid][0] = {curid,0};
  for(int pw = 1;pw <= 20;pw++){
    for(int i = 0; i <= curid;i++){
      st[i][pw] = {st[st[i][pw - 1].F][pw - 1].F, max(st[st[i][pw - 1].F][pw - 1].S,st[i][pw - 1].S)};
    }
  }
  dfs(curid,curid);
}
int getMinimumFuelCapacity(int X, int Y) {
  return ((find(X) != find(Y) || !swp[find(X)]) ? -1 : lca(X,Y));
}

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