Submission #1240711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240711		SalihSahin	Longest Trip (IOI23_longesttrip)	C++20	25 / 100	9 ms	460 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 == 1){
      vector<vector<int> > paths;
      for(int i = 0; i < N; i++){
         paths.pb({i});
      }

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

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

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

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

         if(paths.size() % 3 >= 1){
            npaths.pb(paths[paths.size()-1]);
         }
         if(paths.size() % 3 >= 2){
            npaths.pb(paths[paths.size()-2]);
         }

         paths = npaths;
      }

      if(paths[1].size() > paths[0].size()) swap(paths[0], paths[1]);
      return paths[0];
   }

   return {};
}

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