Submission #1073369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073369		Unforgettablepl	Longest Trip (IOI23_longesttrip)	C++17	60 / 100	936 ms	1556 KiB

longesttrip

#pragma GCC optimize("Ofast","unroll-all-loops")
#include "longesttrip.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> longest_trip(int N,int D){
    vector<vector<int>> adj(N);
    vector areConnected(N,vector<bool>(N));
    for(int i=0;i<N;i++) {
        for(int j=i+1;j<N;j++) {
            if(are_connected({i},{j})) {
                adj[i].emplace_back(j);
                adj[j].emplace_back(i);
                areConnected[i][j]=areConnected[j][i]=true;
            }
        }
    }
    {
        // Case 1 if two components
        int isTwo = -1;
        {
            vector<bool> visited(N);
            int curr = 0;
            function<void(int)> dfs = [&](int x) {
                if(visited[x])return;
                visited[x]=true;
                curr++;
                for(int&i:adj[x])dfs(i);
            };
            dfs(0);
            if(curr!=N) {
                if(curr>=N-curr)isTwo=0;
                else {
                    for(int i=0;i<N;i++) {
                        if(!visited[i]){
                            isTwo=i;break;
                        }
                    }
                }
            }
        }
        if(isTwo!=-1) {
            vector<bool> visited(N);
            vector<int> ans;
            function<void(int)> dfs = [&](int x) {
                visited[x]=true;
                ans.emplace_back(x);
                for(int&i:adj[x])if(!visited[i]) {
                    dfs(i);
                    return;
                }
            };
            dfs(isTwo);
            return ans;
        }
    }
    vector<vector<int>> path(3);
    vector<bool> visited(N);
    function<int(int,int)> dfs = [&](int x,int def) {
        visited[x]=true;
        int state = def;
        int children = 0;
        for(int&i:adj[x])if(!visited[i]) {
            children++;
            if(children==2) {
                assert(dfs(i,2)==2);
                state=0;
                break;
            }
            auto ans = dfs(i,def);
            if(ans==0) {
                state = 0;
                break;
            }
        }
        path[state].emplace_back(x);
        return state;
    };
    auto curr = dfs(0,1);
    if(curr==1) {
        return path[1];
    }
    assert(curr==0);
    if(path[0].size()==1) {
        vector<int> ans = path[1];
        ans.emplace_back(path[0][0]);
        reverse(path[2].begin(),path[2].end());
        for(int&i:path[2])ans.emplace_back(i);
        return ans;
    }
    if(!areConnected[path[0][1]][path[1][0]])swap(path[1],path[2]);
    assert(areConnected[path[0][1]][path[1][0]]);
    path[1].emplace_back(path[0][0]);
    path[0].erase(path[0].begin());
    reverse(path[0].begin(),path[0].end());
    reverse(path[2].begin(),path[2].end());
    auto ans = path[0];
    for(int&i:path[1])ans.emplace_back(i);
    for(int&i:path[2])ans.emplace_back(i);
    assert(ans.size()==N);
    return ans;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from longesttrip.cpp:3:
longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:100:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |     assert(ans.size()==N);
      |            ~~~~~~~~~~^~~

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