Submission #1060026

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060026		noyancanturk	Longest Trip (IOI23_longesttrip)	C++17	5 / 100	7 ms	440 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;
    vector<int>trip;
    trip.pb(0);
    int root1=0,root2=0;
    for(int i=0;i+1<n;i++){
        bool ok=are_connected({i},{i+1});
        if(!ok){
            root1=i,root2=i+1;
            break;
        }else{
            trip.pb(i+1);
        }
    }
    if(trip.size()==n)return trip;
    vector<int>cmp1,cmp2;
    //cerr<<"roots "<<root1<<" "<<root2<<"\n";
    cmp1.pb(root1);
    cmp2.pb(root2);
    for(int i=0;i<n;i++){
        if(i==root1||i==root2)continue;
        bool ok=are_connected({root1},{i});
        if(ok){
            //cerr<<i<<" in cmp1\n";
            cmp1.pb(i);
        }else{
            //cerr<<i<<" in cmp2\n";
            cmp2.pb(i);
        }
    }
    if(cmp2.size()<cmp1.size()){
        swap(cmp1,cmp2);
        swap(root1,root2);
    }
    int link=-1;
    for(int i:cmp1){
        bool ok=are_connected({i},cmp2);
        if(ok){
            link=i;
            break;
        }
    }
    if(link==-1){
        return cmp2;
    }
    //cerr<<"found link "<<link<<"\n";
    vector<int>path;
    for(int i:cmp1){
        if(i!=link)path.pb(i);
    }
    path.pb(link);
    for(int i:cmp2){
        if(i!=link)path.pb(i);
    }
    return path;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:25:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     if(trip.size()==n)return trip;
      |        ~~~~~~~~~~~^~~

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