Submission #1065130

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065130		vjudge1	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	905 ms	1480 KiB

longesttrip

#include "longesttrip.h"
#include<bits/stdc++.h>
using namespace std;
vector<int>adj[256];
bitset<256>vis;
void dfs(int n){
    if(vis[n])return;
    vis[n]=1;
    for(auto i:adj[n])
        dfs(i);
}
vector<int>path;
void dfs2(int n){
    path.push_back(n);
    vis[n]=1;
    for(auto i:adj[n])
        if(!vis[i])
            return dfs2(i);
}
mt19937 rng(1272842334);
vector<int> longest_trip(int N, int D){
    for(int i=0;i<N;i++)
        adj[i].clear();
    for(int i=1;i<N;i++) for(int j=i;j--;)
        if(are_connected({i},{j}))
            adj[i].push_back(j),
            adj[j].push_back(i);
    vis.reset();
    path.clear();
    int nod=rng()%N;
    dfs2(nod);
    if(path.size()==N)
        return path;
    for(auto x:adj[nod])
        if(!vis[x]) {
            vector<int>v2;
            vis[x]=1;
            for(int i=0;i<N;i++)
                if(!vis[i])v2.push_back(i);
            v2.push_back(x);
            for(auto i:path)
                v2.push_back(i);
            return v2;
        }
    vector<int>b;
    for(int i=0;i<N;i++)
        if(!vis[i])
            b.push_back(i);
    return path.size()>b.size()?path:b;
}

Compilation message (stderr)

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

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