Submission #1065160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065160		vjudge1	Longest Trip (IOI23_longesttrip)	C++17	70 / 100	99 ms	968 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[256];
vector<int>path,yettovis;
int findit(vector<int>v,int n){
    if(v.size()==1)return v[0];
    vector<int>v1,v2;
    for(auto i:v)
        v1.push_back(i),
        swap(v1,v2);
    if(are_connected(v1,{n}))
        return findit(v1,n);
    return findit(v2,n);
}
void dfs2(int n){
    path.push_back(n);
    yettovis.erase(lower_bound(yettovis.begin(),yettovis.end(),n));
    if(yettovis.empty())return;
    if(are_connected(yettovis,{n}))
        return dfs2(findit(yettovis,n));
}
vector<int> longest_trip(int N, int D){
    vector<int>cc1{0},cc2;
    for(int i=1;i<N;i++)
        if(are_connected(cc1,{i})) {
            cc1.push_back(i);
        } else cc2.push_back(i);
    if(cc2.size()&&!are_connected(cc1,cc2)){
        return cc1.size()<cc2.size()?cc2:cc1;
    }
    path.clear();
    yettovis.clear();
    for(int i=0;i<N;i++)
        yettovis.push_back(i);
    dfs2(0);
    if(path.size()==N)
        return path;
    while(1) {
        if(are_connected(yettovis,{path[0]})) {
            int x=findit(yettovis,path[0]);
            vector<int>v2;
            for(auto i:yettovis)
                if(i-x)v2.push_back(i);
            v2.push_back(x);
            for(auto i:path)
                v2.push_back(i);
            return v2;
        }
        int x=path[0];
        path.erase(path.begin());
        path.push_back(x);
    }
}

Compilation message (stderr)

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

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