Submission #995828

#	Time	Username	Problem	Language	Result	Execution time	Memory
995828		aaaaaarroz	Longest Trip (IOI23_longesttrip)	C++17	40 / 100	968 ms	1384 KiB

longesttrip

#include <bits/stdc++.h>
using namespace std;
bool are_connected(vector<int> A, vector<int> B);
vector<int> longest_trip(int N, int D){
    vector<vector<int>>graph(N,vector<int>());
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(are_connected({i},{j})){
                graph[i].push_back(j);
                graph[j].push_back(i);
            }
        }
    }
    int max_dist=0;
    vector<int>ans;
    for(int i=0;i<N;i++){
        vector<int>dist(N,-1);
        vector<int>parent(N,-1);
        dist[i]=0;
        stack<int>cola;
        cola.push(i);
        while(!cola.empty()){
            int nodo=cola.top();
            cola.pop();
            for(int vecino:graph[nodo]){
                if(dist[vecino]==-1){
                    parent[vecino]=nodo;
                    dist[vecino]=(dist[nodo]+1);
                    cola.push(vecino);
                    break;
                }
            }
        }
        if(*max_element(dist.begin(),dist.end())>max_dist){
            max_dist=*max_element(dist.begin(),dist.end());
            vector<int>path;
            int best_node;
            for(int j=0;j<N;j++){
                if(dist[j]==max_dist){
                    best_node=j;
                }
            }
            path.push_back(best_node);
            while(parent[best_node]!=-1){
                best_node=parent[best_node];
                path.push_back(best_node);
            }
            ans=path;
        }
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

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