oj.uz

Submission #492190

# Submission time Handle Problem Language Result Execution time Memory
492190 2021-12-05T20:37:29 Z eNGy Dreaming (IOI13_dreaming) C++17
0 / 100
 1000 ms 30124 KB 
#include "dreaming.h"
#include <bits/stdc++.h>
#define c(x) (cerr << __LINE__ << ": " << #x << ' ' << (x) << endl, (x))
#define vis() (cerr << __LINE__ << endl)

using namespace std;

long long D;

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

void massimi(long long &max1, long long &max2, long long &max3, long long l){
	
}

void dfs(int n, vector<bool> &V, vector<trail> trails[], vector<long long> &d){
	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]){
			d[v] = d[n] + t;
			dfs(v, V, trails, d);
		}
	}
}

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

long long massimo(int n, vector<bool> &V, vector<trail> trails[]){
	if(trails[n].size() == 0){
		return 0;
	}
	
	vector<long long> d(D);
	d[n] = 0;
	
	dfs(n, V, trails, d);
	
	int E1 = indice_Dmax(d);
	d[E1] = 0;
	
	vector<bool> V2(D, false);
	dfs(E1, V2, trails, d);
	
	int E2 = indice_Dmax(d);
	long long D = d[E2];
	long long sol = D;
	
	for(int i=0; i<D; i++){
		sol = min(sol, max(d[i], D-d[i]));
	}
	
	return sol;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]){
	D = N;
	
	vector<trail> trails[N];
	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, false);
	
	long long max1 = 0, max2 = 0, max3 = 0;
	for(int i=0; i<N; i++){
		if(!V[i]){
			long long l = massimo(i, V, trails);
			if(max1 < l){
				max3 = max2;
				max2 = max1;
				max1 = l;
			}else if(max2 < l){
				max3 = max2;
				max2 = l;
			}else if(max3 < l){
				max3 = l;
			}
		}
	}
	
	return max(max1 + max2 + L, max2 + max3 + 2*L);
}

Compilation message

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

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 30124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 30124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 6540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 30124 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -