| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1059963 | epicci23 | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;
#include "longesttrip.h"
vector<int> v[300];
vector<int> vis(300,0),depth(300,-1),topo;
int ord[300],int max_c,max_ans,max_a,max_b;
vector<int> aa,bb;
void topo_sort(int c){
if(vis[c]) return;
vis[c]=1;
for(int x:v[c]) topo_sort(x);
topo.push_back(c);
}
void dfs(int c,int p){
if(vis[c]) return;
vis[c]=1;
sort(all(v[c]),[&](int a,int b){
return ord[a]<ord[b];
});
for(int x:v[c]){
dfs(x);
depth[c]=max(depth[c],depth[x]);
}
depth[c]++;
vector<array<int,2>> takla;
for(int x:v[c]){
if(x==p) continue;
takla.push_back({depth[x],x});
}
sort(all(takla));
reverse(all(takla));
if(sz(takla)<=1) return;
if(takla[0][0]+takla[1][0]+1>max_ans){
max_ans=takla[0][0]+takla[1][0]+1;
max_c=c;
max_a=takla[0][1];
max_b=takla[1][1];
}
}
void go_leaf(int c,int t){
int kid=-1,maxi=-1;
for(int x:v[c]){
if(depth[x]>depth[c]) continue;
if(depth[x]>maxi){
maxi=depth[x];
kid=x;
}
}
if(kid!=-1) go_leaf(kid,t);
if(t) aa.push_back(c);
else bb.push_back(c);
}
vector<int> construct(int c){
vector<int> res;
topo.clear();aa.clear();bb.clear();
vis.assign(300,0);
depth.assign(300,-1);
topo_sort(c);
reverse(all(topo));
for(int i=0;i<sz(topo);i++) ord[topo[i]]=i;
vis.assign(300,0);
max_a=max_b=max_ans=max_c=-1;
dfs(c);
vis.assign(300,0);
if(max_a!=-1) go_leaf(max_a,1);
vis.assign(300,0);
if(max_b!=-1) go_leaf(max_b,0);
if(max_a!=-1){
aa.push_back(max_c);
reverse(all(bb));
aa+=bb;
if(sz(aa)>sz(res)) res=aa;
}
aa.clear();
go_leaf(c,1);
if(sz(aa)>sz(res)) res=aa;
return res;
}
vector<int> longest_trip(int n, int d){
if(d==3){
vector<int> res(n,0);
iota(all(res),0);
return res;
}
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
if(are_connected(i,j)){
v[i].push_back(j);
v[j].push_back(i);
}
}
}
vector<int> ans;
for(int i=0;i<n;i++){
vector<int> x=construct(i);
if(sz(x)>sz(ans)) ans=x;
}
return ans;
}
/*void _(){
}
int32_t main(){
cin.tie(0); ios::sync_with_stdio(0);
int tc=1;//cin >> tc;
while(tc--) _();
return 0;
}*/