Submission #1217807

#TimeUsernameProblemLanguageResultExecution timeMemory
1217807im2xtreme가장 긴 여행 (IOI23_longesttrip)C++20
0 / 100
1084 ms672 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...