제출 #1231684

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231684		ericl23302	가장 긴 여행 (IOI23_longesttrip)	C++20	40 / 100	438 ms	752 KiB

longesttrip

#include "longesttrip.h"
#include <bits/stdc++.h>

using namespace std;

void dfs(vector<vector<int>> &adjacency, vector<int> &best, vector<bool> &visited, vector<int> &seq, int cur) {
    visited[cur] = true;
    seq.push_back(cur);
    for (auto &child : adjacency[cur]) {
        if (visited[child]) continue;
        dfs(adjacency, best, visited, seq, child);
    }

    if (seq.size() > best.size()) {
        best.clear();
        for (int &i : seq) best.push_back(i);
    }

    seq.pop_back();
}

std::vector<int> longest_trip(int N, int D)
{
    vector<vector<int>> adjacency(N);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            if (are_connected(vector<int>{i}, vector<int>{j})) adjacency[i].push_back(j), adjacency[j].push_back(i);
        }
    }

    vector<int> best;
    for (int i = 0; i < N; ++i) {
        vector<bool> visited(N, false);
        vector<int> seq;
        dfs(adjacency, best, visited, seq, i);
    }

    return best;
}

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