제출 #1288347

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288347		Faisal_Saqib	자매 도시 (APIO20_swap)	C++20	37 / 100	2095 ms	16072 KiB

swap

#include "swap.h"

#include <vector>
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> ord;
void init(int N, int M,
          std::vector<int> U, std::vector<int> V, std::vector<int> W) {
  // vector<int> deg(N+1);
  n=N;
  for(int i=0;i<M;i++)
  {
    ord.push_back({W[i],U[i],V[i]});
    // deg[U[i]]++;
    // deg[V[i]]++;
  }
  sort(begin(ord),end(ord));
}
/*
0 1 4
0 2 4
1 2 1
1 3 2
1 4 10
2 3 3
*/
const int N=1e5+100;
int par[N],sz[N],cyc[N],deg[N],mx[N];
int get(int x)
{
  if(par[x]==x)return x;
  return par[x]=get(par[x]);
}
void merge(int x,int y)
{
  deg[x]++;
  deg[y]++;
  int px=get(x),py=get(y);
    mx[px]=max(mx[px],deg[x]);
    mx[py]=max(mx[py],deg[y]);
  if(px==py)
  {
    mx[px]=max(mx[px],mx[py]);
    cyc[px]++;
    return;
  }
  sz[px]+=sz[py];
  mx[px]=max(mx[px],mx[py]);
  cyc[px]+=cyc[py];
  par[py]=px;
}
int getMinimumFuelCapacity(int x, int y) {
  for(int i=0;i<n;i++)
  {
    par[i]=i;
    sz[i]=1;
    cyc[i]=0;
    deg[i]=0;
    mx[i]=0;
  }
  for(int i=0;i<ord.size();i++)
  {
    merge(ord[i][1],ord[i][2]);
    if(get(x)==get(y) and (mx[get(x)]>=3 or cyc[get(x)]>0))
    {
      return ord[i][0];
    }
  }
  return -1;
  // return ;
}

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