Submission #1065127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065127		vjudge1	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	902 ms	1420 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;
    }
    for(int i=0;i<N;i++) {
        vis.reset();
        path.clear();
        dfs2(i);
        if(path.size()==N)
            return path;
        for(auto x:adj[i])
            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: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:41:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |         if(path.size()==N)
      |            ~~~~~~~~~~~^~~

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