제출 #1240561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240561		SalihSahin	가장 긴 여행 (IOI23_longesttrip)	C++20	5 / 100	4 ms	408 KiB

longesttrip

#include "bits/stdc++.h"
#include "longesttrip.h"
#define pb push_back
using namespace std;


vector<int> longest_trip(int N, int D){
   if(D == 3){
      vector<int> v;
      for(int i = 0; i < N; i++){
         v.pb(i);
      }
      return v;
   }
   if(D == 2){
      vector<vector<int> > paths;
      for(int i = 0; i + 2 < N; i++){
         bool c1 = are_connected({i}, {i+1});
         bool c2 = are_connected({i+1}, {i+2});
         bool c3 = are_connected({i}, {i+2});

         if(c1 && c2) paths.pb({i, i+1, i+2});
         else if(c1 && c3) paths.pb({i+1, i, i+2});
         else if(c2 && c3) paths.pb({i, i+2, i+1});
      }
      if(N%3 >= 1){
         vector<int> lst = paths[paths.size()-1];
         int a = lst[0], c = lst.back();
         int b = N-1;

         bool c1 = are_connected({a}, {b});
         bool c2 = are_connected({a}, {c});
         bool c3 = are_connected({b}, {c});

         if(c1 && c2){
            reverse(lst.begin(), lst.end());
            // c .... a
            lst.pb(b);
            paths.pop_back();
            paths.pb(lst);
         }
         else if(c1 && c3){
            lst.pb(b);
            paths.pop_back();
            paths.pb(lst);
         }
         else if(c2 && c3){
            lst.pb(b);
            paths.pop_back();
            paths.pb(lst);
         }
      }

      if(N%3 >= 2){
         vector<int> lst = paths[paths.size()-1];
         int a = lst[0], c = lst.back();
         int b = N-2;

         bool c1 = are_connected({a}, {b});
         bool c2 = are_connected({a}, {c});
         bool c3 = are_connected({b}, {c});

         if(c1 && c2){
            reverse(lst.begin(), lst.end());
            // c .... a
            lst.pb(b);
            paths.pop_back();
            paths.pb(lst);
         }
         else if(c1 && c3){
            lst.pb(b);
            paths.pop_back();
            paths.pb(lst);
         }
         else if(c2 && c3){
            lst.pb(b);
            paths.pop_back();
            paths.pb(lst);
         }
      }

      while(paths.size() > 1){
         vector<vector<int> > npaths;

         for(int i = 0; i + 1 < paths.size(); i += 2){
            int a = paths[i][0], b = paths[i].back(), c = paths[i+1][0];

            bool c1 = are_connected({a}, {b});
            bool c2 = are_connected({a}, {c});
            bool c3 = are_connected({b}, {c});

            if(c1 && c2){
               vector<int> v = paths[i];
               reverse(v.begin(), v.end());
               for(auto itr: paths[i+1]) v.pb(itr);
               npaths.pb(v);
            }
            else if(c1 && c3){
               vector<int> v = paths[i];
               for(auto itr: paths[i+1]) v.pb(itr);
               npaths.pb(v);
            }
            else if(c2 && c3){
               vector<int> v = paths[i];
               for(auto itr: paths[i+1]) v.pb(itr);
               npaths.pb(v);
            }
         }

         paths = npaths;
      }

      return paths[0];
   }

   return {};
}

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