Submission #1072443

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072443		HorizonWest	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	996 ms	1608 KiB

longesttrip

#include <iostream>
#include <complex>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <functional>
#include <bitset>
#include <queue>
#include <map>
#include <stack>
#include <cmath>
#include <cstdint>
#include <cassert>
#include "longesttrip.h"
using namespace std;
vector <int> longest_trip(int n, int d)
{
    vector <vector<int>> v(n, vector <int> ()),
        s(n, vector <int> (n, -1));

    auto add = [&] (int a, int b) -> void {
        if(s[a][b] == -1){
            s[a][b] = s[b][a] = 1;
            v[a].push_back(b);
            v[b].push_back(a);
        }
    };

    if(d == 3){
        for(int i = 0; i < n; i++){
            for(int j = i+1; j < n; j++) {
                add(i, j);
            }
        }
    }else if(d == 2){
        for(int i = 0; i < n; i++)
        {
            for(int j = i+1; j < n; j++) 
            {
                if(s[i][j] == -1){
                    s[i][j] = are_connected({ i }, { j }); 

                    if(s[i][j] == 1){
                        s[i][j] = -1; add(i, j);
                    }
                }
            }
        }
    } else if(d == 1){
        for(int i = 0; i < n; i++)
        {
            for(int j = i+1; j < n; j++)
            {
                if(s[i][j] == -1){
                    s[i][j] = are_connected({ i }, { j }); 
                    if(s[i][j] == 1) {
                        s[i][j] = -1;
                        add(i, j);
                    }
                }
            }
        }
    }

    vector <int> pass(n), ans, path; 

    auto dfs = [&] (auto dfs, int node, int parent) -> void
    {
        path.push_back(node); pass[node] = 1;
        if(path.size() > ans.size()) ans = path;

        for(auto& u : v[node]) if(!pass[u]){
            if(v[u].size() != n) dfs(dfs, u, node); 
        }

        for(auto& u : v[node]) if(!pass[u])
        {
            dfs(dfs, u, node); 
        }

        path.pop_back(); 
    };

    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){ 
            pass[j] = 0;   
        }

        if(ans.size() == n) break;
        dfs(dfs, i, i);
    }

    return ans;
}

Compilation message (stderr)

longesttrip.cpp: In function 'std::vector<int> longest_trip(int, int)':
longesttrip.cpp:89:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   89 |         if(ans.size() == n) break;
      |            ~~~~~~~~~~~^~~~
longesttrip.cpp: In instantiation of 'longest_trip(int, int)::<lambda(auto:1, int, int)> [with auto:1 = longest_trip(int, int)::<lambda(auto:1, int, int)>]':
longesttrip.cpp:90:22:   required from here
longesttrip.cpp:73:28: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   73 |             if(v[u].size() != n) dfs(dfs, u, node);
      |                ~~~~~~~~~~~~^~~~

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