Submission #852317

#	Time	Username	Problem	Language	Result	Execution time	Memory
852317		Ludissey	Longest Trip (IOI23_longesttrip)	C++17	0 / 100	1059 ms	1576 KiB

longesttrip

#include <bits/stdc++.h>
#include "longesttrip.h"
using namespace std;

vector<vector<int>> neigh;
vector<bool> visited;

vector<int> longest_path(int i){
    if(visited[i]) return {};
    visited[i]=true;
    vector<int> longest_vector;
    for (int c : neigh[i])
    {
        vector<int> c_longest=longest_path(c);
        if(c_longest.size()>longest_vector.size()) longest_vector=c_longest;
    }
    longest_vector.push_back(i);
    return longest_vector;
}

std::vector<int> longest_trip(int N, int D)
{
    vector<int> ret;
    neigh.clear();
    neigh.resize(N);
    for (int i = 0; i < N-1; i++){
        for (int j = i+1; j < N; j++)
        {
            if(are_connected({i}, {j})){
                neigh[i].push_back(j);
                neigh[j].push_back(i);
            }
        }
    }
    vector<int> longest_vector;
    for (int i = 0; i < N; i++){
        visited.clear();
        visited.resize(N);
        vector<int> c_longest=longest_path(i);
        if(c_longest.size()>longest_vector.size()) longest_vector=c_longest;
    }
    return longest_vector;
}

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