Submission #1072399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072399		HorizonWest	Longest Trip (IOI23_longesttrip)	C++17	30 / 100	997 ms	1736 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] == 0){
                        for(int k = 0; k < n; k++){
                            add(i, k); add(j, k);
                        }
                    }else{
                        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])
        {
            dfs(dfs, u, node); 
        }

        path.pop_back(); 
    };

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

        dfs(dfs, i, i);
    }

    return ans;
}

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