| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 897065 | irmuun | 가장 긴 여행 (IOI23_longesttrip) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "longesttrip.h"
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
vector<int>longest_trip(int N, int D){
vector<int>ans;
if(D==3){
vector<int>ans(N);
iota(all(ans),0);
return ans;
}
if(D==2){
vector<int>ans;
ans.pb(0);
int l=0,r=0;
int x;
for(int i=1;i<N;i++){
if(are_connected({0},{i})==true){
ans.pb(i);
x=i;
r=i;
break;
}
}
for(int i=1;i<N;i++){
if(i!=x){
if(are_connected({l},{i})){
ans.insert(ans.begin(),i);
l=i;
}
else{
ans.pb(i);
r=i;
}
}
}
return ans;
}
vector<int>v,u;
v.pb(0);
u.pb(1);
for(int i=2;i<N;i++){
if(are_connected({v.back()},{i})==true){
v.pb(i);
}
else if(are_connected({u.back()},{i})==true){
u.pb(i);
}
else{
reverse(all(u));
v.insert(v.end(),all(u));
u={i};
}
}
if(are_connected(v,u)==false){
if(v.size()>=u.size()){
return v;
}
return u;
}
//now need combine 2 cycles
if(v.size()>=2&&u.size()>=2){
if(are_connected({v[0],v.back()},{u[0],u.back()})==true){
if(are_connected({v[0]},{u[0]})){
reverse(all(v));
v.insert(v.end(),all(u));
}
else if(are_connected({v[0]},{u.back()})){
reverse(all(v));
reverse(all(u));
v.insert(v.end(),all(u));
}
else if(are_connected({v.back()},{u[0]})){
v.insert(v.end(),all(u));
}
else if(are_connected({v.back()},{u.back()})){
reverse(all(u));
v.insert(v.end(),all(u));
}
return v;
}
}
vector<int>v1=v,u1=u;
while(v1.size()>1){
vector<int>l,r;
for(int i=0;i<v1.size()/2;i++){
l.pb(v1[i]);
}
for(int i=v1.size()/2;i<v1.size();i++){
r.pb(v1[i]);
}
if(are_connected(l,u1)==true){
v1=l;
}
else{
v1=r;
}
}
while(u1.size()>1){
vector<int>l,r;
for(int i=0;i<u1.size()/2;i++){
l.pb(u1[i]);
}
for(int i=u1.size()/2;i<u1.size();i++){
r.pb(u1[i]);
}
if(are_connected(v1,l)==true){
u1=l;
}
else{
u1=r;
}
}
for(int i=0;i<v.size();i++){
if(v[i]==v1[0]){
rotate(v.begin(),v.begin()+i,v.end());
break;
}
}
for(int i=0;i<u.size();i++){
if(u[i]==u1[0]){
rotate(u.begin(),u.begin()+i,u.end());
break;
}
}
reverse(all(v));
v.insert(v.end(),all(u));b
return v;
}