oj.uz

Submission #995813

# Submission time Handle Problem Language Result Execution time Memory
995813 2024-06-09T23:40:53 Z aaaaaarroz Longest Trip (IOI23_longesttrip) C++17
0 / 100
 7 ms 344 KB 
#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);
				}
			}
		}
		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 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 344 KB Output is correct
2 Incorrect 1 ms 344 KB Incorrect
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Incorrect
2 Halted 0 ms 0 KB -