Submission #1212587

#TimeUsernameProblemLanguageResultExecution timeMemory
1212587Aviansh가장 긴 여행 (IOI23_longesttrip)C++20
15 / 100
329 ms472 KiB
#include "longesttrip.h" #include <bits/stdc++.h> using namespace std; vector<int> longest_trip(int n, int D) { if(D==3){ vector<int>ans(n); iota(ans.begin(),ans.end(),0); return ans; } if(D==2){ set<int>lef; for(int i = 0;i<n;i++){ lef.insert(i); } vector<int>ans; ans.push_back(0); lef.erase(0); while(lef.size()>1){ if(are_connected({ans.back()},{*lef.begin()})){ ans.push_back(*lef.begin()); lef.erase(lef.begin()); } else{ ans.push_back(*(++lef.begin())); lef.erase(++lef.begin()); } } if(are_connected({*lef.begin()},{ans.back()})){ ans.push_back(*lef.begin()); return ans; } ans.insert(ans.begin(),*lef.begin()); return ans; } assert(D==1); bool adj[n][n]; for(int i = 0;i<n;i++){ fill(adj[i],adj[i]+n,0); } for(int i = 0;i<n;i++){ for(int j = i+1;j<n;j++){ if(are_connected({i},{j})){ adj[i][j]=adj[j][i]=1; } } } vector<int>pt1,pt2; pt1.push_back(0); for(int i = 1;i<n;i++){ int prev1 = pt1.back(); if(adj[prev1][i]){ pt1.push_back(i); continue; } //not adjacent. if(pt2.size()){ int prev2 = pt2.back(); if(adj[prev2][i]){ pt2.push_back(i); } else{ assert(adj[prev1][prev2]); reverse(pt2.begin(),pt2.end()); pt1.insert(pt1.end(),pt2.begin(),pt2.end()); pt2.clear(); i--; continue; } } else{ pt2.push_back(i); } } int mxi, mxj; mxi=-1; mxj=-1; for(int i = 0;i<pt1.size();i++){ for(int j = 0;j<pt2.size();j++){ if(adj[pt1[i]][pt2[j]]){ if(mxi==-1){ mxi=i; mxj=j; continue; } int ollen = max(mxi+1,(int)pt1.size()-mxi)+max(mxj+1,(int)pt2.size()-mxj); int newlen = max(i+1,(int)pt1.size()-i)+max(j+1,(int)pt2.size()-j); if(newlen>ollen){ mxi=i; mxj=j; } } } } if(mxi==-1){ if(pt1.size()>pt2.size()){ return pt1; } return pt2; } vector<int>ans; if(mxi+1>pt1.size()-mxi){ for(int i = 0;i<=mxi;i++){ ans.push_back(pt1[i]); } } else{ for(int i = pt1.size()-1;i>=mxi;i--){ ans.push_back(pt1[i]); } } if(mxj+1>pt2.size()-mxj){ for(int i = 0;i<=mxj;i++){ ans.push_back(pt2[i]); } } else{ for(int i = pt2.size()-1;i>=mxj;i--){ ans.push_back(pt2[i]); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...