제출 #1231683

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231683		ericl23302	Longest Trip (IOI23_longesttrip)	C++20	40 / 100	430 ms	760 KiB

longesttrip

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

using namespace std;

vector<int> best;

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

    if (last && 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)
{
    best.clear();
    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);
        }
    }

    for (int i = 0; i < N; ++i) {
        vector<bool> visited(N, false);
        vector<int> seq;
        dfs(adjacency, 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