Submission #1240817

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240817		SalihSahin	Longest Trip (IOI23_longesttrip)	C++20	70 / 100	8 ms	476 KiB

longesttrip

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

vector<int> longest_trip(int N, int D){
   mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
   if(D == 1){
      vector<vector<int> > paths;
      for(int i = 0; i < N; i++){
         paths.pb({i});
      }
      shuffle(paths.begin(), paths.end(), rng);

      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 = 0;

            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]);
               continue;
            }
            else{
               c2 = are_connected({a}, {c});
            }

            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{
               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]);
            }
         }

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

         paths = npaths;
         shuffle(paths.begin(), paths.end(), rng);
      }

      bool check = are_connected(paths[0], paths[1]);
      if(paths[1].size() > paths[0].size()) swap(paths[0], paths[1]);

      if(!check){
         return paths[0];
      }
      else{
         if(paths[1].size() == 1){ // bu if buglı
            int a = paths[0][0], b = paths[0].back(), c = paths[1][0];
            bool c1 = are_connected({a}, {b});
            bool c2 = are_connected({b}, {c});
            bool c3 = are_connected({c}, {a});

            if(c2){
               paths[0].pb(c);
               return paths[0];
            }
            if(c3){
               reverse(paths[0].begin(), paths[0].end());
               paths[0].pb(c);
               return paths[0];
            }

            int l = 0, r = paths[0].size()-1;
            while(l < r){
               int m = (l + r)/2;

               vector<int> v;
               for(int i = 0; i <= m; i++){
                  v.pb(paths[0][i]);
               }
               bool check = are_connected(v, {c});
               if(check) r = m;
               else l = m+1;
            }
            int x = paths[0][l];

            vector<int> updpath;
            for(auto itr: paths[0]){
               updpath.pb(itr);
               if(itr == x) break;
            }
            updpath.pb(c);
            reverse(updpath.begin(), updpath.end());
            reverse(paths[0].begin(), paths[0].end());
            for(auto itr: paths[0]){
               if(itr == x) break;
               updpath.pb(itr);
            }
            return updpath;
         }
         else{
            int a = paths[0][0], b = paths[0].back(), c = paths[1][0], d = paths[1].back();
            bool c2 = are_connected({b}, {c});
            bool c3 = 0;

            if(c2){
               vector<int> v = paths[0];
               for(auto itr: paths[1]) v.pb(itr);
               return v;
            }
            else{
               c3 = are_connected({c}, {a});
            }

            if(c3){
               vector<int> v = paths[0];
               reverse(v.begin(), v.end());
               for(auto itr: paths[1]) v.pb(itr);
               return v;
            }
            bool c5 = are_connected({a}, {d});
            bool c6 = 0;

            if(c5){
               vector<int> v = paths[0];
               reverse(v.begin(), v.end());
               reverse(paths[1].begin(), paths[1].end());
               for(auto itr: paths[1]) v.pb(itr);
               return v;
            }
            else{
               c6 = are_connected({b}, {d});
            }
            
            if(c6){
               vector<int> v = paths[1];
               reverse(paths[0].begin(), paths[0].end());
               for(auto itr: paths[0]) v.pb(itr);
               return v;
            }

            // şimdi ikisinin de cycle olduğunu biliyoruz

            pair<int, int> p = {-1, -1};
            int l = 0, r = paths[1].size()-1;
            while(l < r){
               int m = (l + r)/2;

               vector<int> v;
               for(int i = 0; i <= m; i++){
                  v.pb(paths[1][i]);
               }
               bool check = are_connected(paths[0], v);
               if(check) r = m;
               else l = m+1;
            }
            int sec = paths[1][l];

            l = 0, r = paths[0].size()-1;
            while(l < r){
               int m = (l + r)/2;

               vector<int> v;
               for(int i = 0; i <= m; i++){
                  v.pb(paths[0][i]);
               }
               bool check = are_connected({sec}, v);
               if(check) r = m;
               else l = m+1;
            }
            int fir = paths[0][l];

            p = {fir, sec};

            vector<int> ans;
            for(auto itr: paths[0]){
               if(itr == p.first) break;
               ans.pb(itr);
            }
            reverse(ans.begin(), ans.end());
            reverse(paths[0].begin(), paths[0].end());
            for(auto itr: paths[0]){
               ans.pb(itr);
               if(itr == p.first) break;
            } // son eleman p.first
            
            vector<int> ans2;
            for(auto itr: paths[1]){
               if(itr == p.second) break;
               ans2.pb(itr);
            }
            reverse(ans2.begin(), ans2.end());
            reverse(paths[1].begin(), paths[1].end());
            for(auto itr: paths[1]){
               ans2.pb(itr);
               if(itr == p.second) break;
            } // son eleman p.second

            vector<int> v = ans;
            reverse(ans2.begin(), ans2.end());
            for(auto itr: ans2) v.pb(itr);
            return v;
         }
      }
   }

   return {};
}

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