Submission #1065128

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065128		vjudge1	Longest Trip (IOI23_longesttrip)	C++17	15 / 100	865 ms	1380 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);
}
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();
    dfs(0);
    if(vis.count()!=N){
        vector<int>a,b;
        for(int i=0;i<N;i++)
            if(!vis[i])
                a.push_back(i);
            else b.push_back(i);
        return a.size()>b.size()?a:b;
    }
    vis.reset();
    path.clear();
    dfs2(0);
    if(path.size()==N)
        return path;
    for(auto x:adj[0])
        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;
        }
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:29:19: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     if(vis.count()!=N){
      |        ~~~~~~~~~~~^~~
longesttrip.cpp:40:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |     if(path.size()==N)
      |        ~~~~~~~~~~~^~~
longesttrip.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

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