Submission #1065155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065155		vjudge1	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	886 ms	1520 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();
    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();
    int nod=rng()%N;
    dfs2(nod);
    if(path.size()==N)
        return path;
    while(1) {
        for(auto x:adj[path[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;
            }
        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:30:19: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   30 |     if(vis.count()!=N){
      |        ~~~~~~~~~~~^~~
longesttrip.cpp:42:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |     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