Submission #1059934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059934		noyancanturk	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	427 ms	600 KiB

longesttrip

#include "longesttrip.h"

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

#define pb push_back

int n,d;

vector<int> longest_trip(int N, int D)
{
    n=N,d=D;
    if(2<=D){
        deque<int>trip;
        trip.pb(0);
        for(int i=1;i<n;i++){
            bool ok=are_connected({trip.back()},{i});
            if(ok)trip.pb(i);
            else if(trip.size()==1){
                trip.pb(i+1);
                trip.pb(i);
                i++;
            }else{
                trip.push_front(i);
            }
        }
        return vector<int>(trip.begin(),trip.end());
    }
    bool vis[n]{};
    vis[0]=1;
    vector<int>trip;
    trip.pb(0);
    while(trip.size()<(N+1)/2){
        //cerr<<trip.size()<<"\n";
        vector<int>myguys;
        for(int j=0;j<n;j++){
            if(j==trip.back())continue;
            bool ok=are_connected({trip.back()},{j});
            //cerr<<"trying "<<trip.back()<<" "<<j<<"\n";
            if(!ok)myguys.pb(j);
            if(myguys.size()==(N+1)/2){
                return myguys;
            }
            if(ok&&!vis[j]){
                trip.push_back(j);
                vis[j]=1;
                break;
            }
        }
        cerr<<myguys.size()<<" my guys\n";
    }
    return trip;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:33:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     while(trip.size()<(N+1)/2){
      |           ~~~~~~~~~~~^~~~~~~~
longesttrip.cpp:41:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             if(myguys.size()==(N+1)/2){
      |                ~~~~~~~~~~~~~^~~~~~~~~

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