제출 #1217807

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1217807		im2xtreme	가장 긴 여행 (IOI23_longesttrip)	C++20	0 / 100	1084 ms	672 KiB

longesttrip

#include <vector>
#include <algorithm>
using namespace std;

// Provided by the grader
extern bool are_connected(vector<int> A, vector<int> B);

const int MAXN = 256;
vector<int> adj[MAXN];
vector<int> best_path;

void dfs(int node, vector<bool>& visited, vector<int>& path) {
    visited[node] = true;
    path.push_back(node);
    if (path.size() > best_path.size()) {
        best_path = path;
    }
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited, path);
        }
    }
    path.pop_back();
    visited[node] = false;
}

vector<int> longest_trip(int N, int D) {
    // Clear previous data
    for (int i = 0; i < N; ++i) {
        adj[i].clear();
    }
    best_path.clear();

    // Build the adjacency list
    for (int i = 0; i < N; ++i) {
        vector<int> candidates;
        for (int j = i + 1; j < N; ++j) {
            candidates.push_back(j);
        }

        if (candidates.empty()) continue;

        if (are_connected({i}, candidates)) {
            // Binary search to find exact connected nodes
            for (int j : candidates) {
                if (are_connected({i}, {j})) {
                    adj[i].push_back(j);
                    adj[j].push_back(i); // bidirectional
                }
            }
        }
    }

    // Run DFS from each node
    vector<bool> visited(N, false);
    vector<int> path;
    for (int i = 0; i < N; ++i) {
        dfs(i, visited, path);
    }

    return best_path;
}

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