| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1349017 | yyc000123 | 즐거운 행로 (APIO20_fun) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
using namespace std ;
#define g0 get<0>
#define g1 get<1>
#define g2 get<2>
const int N = 505 ;
const int Q = 4e5+5 ;
int arr[N][N] , par[N] , vis[N] , inv[N] ;
vector<tuple<int,int,int>> vt ;
vector<int> nei[N] ;
int p(int k){
if(par[k]<0) return k ;
else return par[k]=p(par[k]) ;
}
void dfs(int node){
for(int i:nei[node]){
if(inv[i] || vis[i]!=-1) continue ;
vis[i]=vis[node]+1 ;
dfs(i) ;
}
}
vector<int> createFunTour(int n , int q){
for(int i=1 ; i<=n ; i++){
for(int j=i+1 ; j<=n ; j++){
arr[i][j]=arr[j][i]=hoursRequired(i,j) ;
vt.push_back({arr[i][j],i,j}) ;
}
}
sort(vt.begin(),vt.end()) ;
memset(par,-1,sizeof(par)) ;
for(int i=0 ; i<vt.size() ; i++){
int u = g1(vt[i]) , v = g2(vt[i]) , pu = p(u) , pv = p(v) ;
if(pu==pv) continue ;
nei[u].push_back(v) ;
nei[v].push_back(u) ;
if(par[pu]<=par[pv]) par[pu]+=par[pv] , par[pv]=pu ;
else par[pv]+=par[pu] , par[pu]=pv ;
}
int root ;
for(int i=0 ; i<n ; i++){
if(nei[i].size()<=2){
root=i ;
break ;
}
}
vector<int> v ;
while(true){
v.push_back(root) ; inv[root]=1 ;
memset(vis,-1,sizeof(vis)) ;
vis[root]=0 ;
dfs(root) ;
int temp = *max_element(vis,vis+n) ;
for(int i=0 ; i<n ; i++){
if(vis[i]==temp){
root=i ;
break ;
}
}
}
return v ;
}