Submission #1195315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195315		Ak_16	Longest Trip (IOI23_longesttrip)	C++20	15 / 100	6 ms	428 KiB

longesttrip

#include <iostream>
#include "longesttrip.h"
#include <vector>
using namespace std;
int adj[500][500];
int ls1[500];
int ls2[500];
int cnt1;
int cnt2;
int tem[500];
vector<int> vec1,vec2,vec3;
bool na1, na2;
int l1,r1,l2,r2;
int mi;


vector<int> longest_trip(int n, int d){
  
  cnt1 = 0;
  cnt2 = 0;
  
  for(int i=0; i<n; i++){ls1[i] = 0; ls2[i] = 0;}
  
  ls1[0] = 0;
  ls2[0] = 1;
  
  cnt1++;
  cnt2++;
  
  for(int i=2; i<n; i++){
    vec1.clear();
    vec2.clear();
    vec3.clear();
    
    vec1.push_back(i);
    vec2.push_back(ls1[cnt1-1]);
    vec3.push_back(ls2[cnt2-1]);
    
    na1 = are_connected(vec1, vec2);
    na2 = are_connected(vec1, vec3);
    
    if(na1){
      ls1[cnt1] = i;
      cnt1++;
    }
    
    else if(na2){
      ls2[cnt2] = i;
      cnt2++;
    }
    
    else {
      for(int j=0; j<cnt2; j++){
        ls1[cnt1+cnt2-1-j] = ls2[j];
      }
      cnt1 += cnt2;
      cnt2 = 1;
      ls2[0] = i;
    }
  }
  
  vec1.clear();
  vec2.clear();
  
  for(int i=0; i<cnt1; i++){
    vec1.push_back(ls1[i]);
  }
  
  for(int i=0; i<cnt2; i++){
    vec2.push_back(ls2[i]);
  }
  
  na1 = are_connected(vec1, vec2);
  
  if(!na1){
    vec3.clear();
    
    if(cnt1>=cnt2){
      for(int i=0; i<cnt1; i++){
        vec3.push_back(ls1[i]);
      }
    }
    
    else {
      for(int i=0; i<cnt2; i++){
        vec3.push_back(ls2[i]);
      }
    }
    
    return vec3;
  }
  
  vec1.clear();
  vec2.clear();
  vec3.clear();
  
  vec1.push_back(ls1[cnt1-1]);
  vec2.push_back(ls2[cnt2-1]);
  vec3.push_back(ls2[0]);
  
  na1 = are_connected(vec1, vec2);
  na2 = are_connected(vec1, vec3);
  
  if(na1){
    for(int j=0; j<cnt2; j++){
        ls1[cnt1+cnt2-1-j] = ls2[j];
      }
      cnt1 += cnt2;
      cnt2 = 0;
      
      vec3.clear();
      for(int i=0; i<cnt1; i++){
        vec3.push_back(ls1[i]);
      }
      return vec3;
  }
  
  if(na2){
    for(int j=0; j<cnt2; j++){
        ls1[cnt1+j] = ls2[j];
      }
      cnt1 += cnt2;
      cnt2 = 0;
      
      vec3.clear();
      for(int i=0; i<cnt1; i++){
        vec3.push_back(ls1[i]);
      }
      return vec3;
  }
  
  for(int i=0; i<cnt1/2; i++){
    swap(ls1[i], ls1[cnt1-1-i]);
  }
  
  vec1.clear();
  vec2.clear();
  vec3.clear();
  
  vec1.push_back(ls1[cnt1-1]);
  vec2.push_back(ls2[cnt2-1]);
  vec3.push_back(ls2[0]);
  
  na1 = are_connected(vec1, vec2);
  na2 = are_connected(vec1, vec3);
  
  if(na1){
    for(int j=0; j<cnt2; j++){
        ls1[cnt1+cnt2-1-j] = ls2[j];
      }
      cnt1 += cnt2;
      cnt2 = 0;
      
      vec3.clear();
      for(int i=0; i<cnt1; i++){
        vec3.push_back(ls1[i]);
      }
      return vec3;
  }
  
  if(na2){
    for(int j=0; j<cnt2; j++){
        ls1[cnt1+j] = ls2[j];
      }
      cnt1 += cnt2;
      cnt2 = 0;
      
      vec3.clear();
      for(int i=0; i<cnt1; i++){
        vec3.push_back(ls1[i]);
      }
      return vec3;
  }
  
  l1 = 0;
  r1 = cnt1-1;
  
  l2 = 0;
  r2 = cnt2-1;
  
  vec2.clear();
  
  for(int i=0; i<cnt2; i++){
    vec2.push_back(ls2[i]);
  }
  
  while(l1<r1){
    mi = (l1+r1)/2;
    vec1.clear();
    for(int i=l1; i<=mi; i++){
      vec1.push_back(ls1[i]);
    }
    
    na1 = are_connected(vec1, vec2);
    if(na1){
      r1 = mi;
    }
    else {
      l1 = mi+1;
    }
  }
  
  vec1.clear();
  
  vec1.push_back(ls1[l1]);
  
  while(l2<r2){
    mi = (l2+r2)/2;
    vec2.clear();
    for(int i=l1; i<=mi; i++){
      vec2.push_back(ls1[i]);
    }
    
    na1 = are_connected(vec1, vec2);
    if(na1){
      r2 = mi;
    }
    else {
      l2 = mi+1;
    }
  }
  
  vec3.clear();
  
  for(int i=1; i<=cnt1; i++){
    vec3.push_back(ls1[(l1+i)%cnt1]);
  }
  
  for(int i=0; i<cnt2; i++){
    vec3.push_back(ls2[(l2+i)%cnt2]);
  }
  
  return vec3;
  
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 25
• Subtask 4: 0 / 60