Submission #1363316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1363316		khanhphucscratch	가장 긴 여행 (IOI23_longesttrip)	C++20	5 / 100	3 ms	412 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;

vector<int> longest_trip(int n, int D)
{
    //Construct two chains
    vector<int> path1 = {0}, path2;
    bool tail_info = 0;
    for(int i = 1; i < n; i++){
        if(path2.size() == 0){
            if(are_connected({path1.back()}, {i}) == 1) path1.push_back(i);
            else path2.push_back(i);
        }
        else{
            if(tail_info == 1){
                if(are_connected({path1.back()}, {i}) == 1) path1.push_back(i);
                else path2.push_back(i);
                tail_info = 0;
            }
            else{
                int x = are_connected({path1.back()}, {i});
                if(x == 1){path1.push_back(i); continue;}
                int y = are_connected({path2.back()}, {i});
                if(y == 1){path2.push_back(i); tail_info = 1;}
                else{
                    //The tail are connected
                    tail_info = (path2.size() == 1);
                    while(path2.size() > 0){
                        path1.push_back(path2.back()); path2.pop_back();
                    }
                    path2.push_back(i);
                }
            }
        }
    }
    //Ok now we have two chain
    if(path1.size() < path2.size()) swap(path1, path2);
    if(path2.size() == 0) return path1;
    if(path2.size() <= 2){
        vector<int> places = {0, path1.size()-1};
        if(path1.size() > 1){
            places.push_back(1);
            places.push_back(path1.size()-2);
        }
        for(int i : places){
            for(int j = 0; j < path2.size(); j++) if(are_connected({path1[i]}, {path2[j]}) == 1){
                if(i+2 < path1.size()) reverse(path1.begin(), path1.end());
                if(i != 0 && i != path1.size()-1) path1.pop_back();
                if(j != path2.size()-1) reverse(path2.begin(), path2.end());
                for(int k : path2) path1.push_back(k);
                return path1;
            }
        }
        return path1;
    }
    else{
        if(are_connected({path1[0]}, {path2[0]}) == 1){
            reverse(path1.begin(), path1.end());
            for(int i : path2) path1.push_back(i);
            return path1;
        }
        if(are_connected({path1.back()}, {path2[0]}) == 1){
            for(int i : path2) path1.push_back(i);
            return path1;
        }
        //Now we could binary search
        if(are_connected(path1, {path2[0]}) == 0){
            swap(path1, path2);
            if(are_connected(path1, {path2[0]}) == 0) return path2; //two clique case
        }
        //path1 is a cycle. We will always be able to construct
        int l = 0, r = path1.size()-1, p = -1;
        while(l <= r){
            int mid = (l+r)/2;
            vector<int> question;
            for(int i = 0; i <= mid; i++) question.push_back(path1[i]);
            if(are_connected(question, {path2[0]}) == 1){p = mid; r = mid-1;}
            else l = mid+1;
        }
        vector<int> ans;
        for(int i = p+1; i < path1.size(); i++) ans.push_back(path1[i]);
        for(int i = 0; i <= p; i++) ans.push_back(path1[i]);
        for(int i : path2) ans.push_back(i);
        return ans;
    }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:41:46: warning: narrowing conversion of '(path1.std::vector<int>::size() - 1)' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   41 |         vector<int> places = {0, path1.size()-1};
      |                                  ~~~~~~~~~~~~^~
longesttrip.cpp:41:46: warning: narrowing conversion of '(path1.std::vector<int>::size() - 1)' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]

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