Submission #492131

#	Time	Username	Problem	Language	Result	Execution time	Memory
492131		eNGy	Dreaming (IOI13_dreaming)	C++17	0 / 100	1099 ms	65540 KiB

dreaming

 #include "dreaming.h"
#include <bits/stdc++.h>
#define c(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)

using namespace std;

struct trail{
	public:
		int v, t;
		
		trail(int v, int t): v(v), t(t) {}
};

int D;

void dfs(int n, vector<trail> trails[], vector<bool> V, vector<int> l){
	V[n] = 1;
	for(int i=0; i<trails[n].size(); i++){
		int v = trails[n][i].v, t = trails[n][i].t;
		if(!V[v]){
			l[v] = l[n] + t;
			dfs(v, trails, V, l);
		}
	}
}

int indice_Dmax(vector<int> l){
	int I = 1;
	for(int i=2; i<=D; i++){
		if(l[i] > l[I]){
			I = i;
		}
	}
	return I;
}

int lunghezza(int n, vector<trail> trails[], vector<bool> V){
	vector<int> l(D);
	dfs(n, trails, V, l);
	
	int E1 = indice_Dmax(l);
	
	dfs(n, trails, vector<bool>(D, false) , l); 
	
	int E2 = indice_Dmax(l);
	int Dmax = l[E2];
	
	int sol = max(l[1], Dmax-l[1]);
	for(int i=2; i<=D; i++){
		sol = max(sol, max(l[i], Dmax-l[i]));
	}
	
	return sol;
}

void massimi(int &max1, int &max2, int &max3, int l){
	if(max1 < l){
		max3 = max2;
		max2 = max1;
		max1 = l;
	}else if(max2 < l){
		max3 = max2;
		max2 = l;
	}else if(max3 < l){
		max3 = l;
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	D = N;
	
	vector<trail> trails[N+1];
	for(int i=0; i<M; i++){
		trails[A[i]].push_back(trail(B[i], T[i]));
		trails[B[i]].push_back(trail(A[i], T[i]));
	}
	
	vector<bool> V(N+1, false);
	int max1=0, max2=0, max3=0;
	for(int i=1; i<=N; i++){
		if(!V[i]){
			massimi(max1, max2, max3, lunghezza(i, trails, V));
		}
	}
	
	return max(max1 + max2 + L, max2 + max3 + L*2);
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs(int, std::vector<trail>*, std::vector<bool>, std::vector<int>)':
dreaming.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<trail>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0; i<trails[n].size(); i++){
      |               ~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int lunghezza(int, std::vector<trail>*, std::vector<bool>)':
dreaming.cpp:42:6: warning: unused variable 'E1' [-Wunused-variable]
   42 |  int E1 = indice_Dmax(l);
      |      ^~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 18
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23