Submission #218876

#	Time	Username	Problem	Language	Result	Execution time	Memory
218876		bigg	Dreaming (IOI13_dreaming)	C++14	18 / 100	70 ms	14452 KiB

dreaming

#include "dreaming.h"
#include<bits/stdc++.h>
using namespace std;
int n, m, l;
vector<pair<int, int> > grafo[112345];
vector<int> comp[112345];
int compid[112345];
int altura[112345];
int centro[112345], maxraio[112345];
int marc1[112345], marc2[112345], marc3[112345];
int maxd, maxdi, qtdcomp, cf, cfi;

void dfs1(int x){
	marc1[x] = 1;
	comp[qtdcomp].push_back(x);
	for(int i = 0; i < grafo[x].size(); i++){
		int viz = grafo[x][i].first;
		if(!marc1[viz]){
			altura[viz] = altura[x] + grafo[x][i].second;
			if(altura[viz] >= maxd){
				maxd = altura[viz];
				maxdi = viz;
			}
			dfs1(viz);
		}


	}

}
void dfs2(int x){
	marc2[x] = 1;
	
	for(int i = 0; i < grafo[x].size(); i++){
		int viz = grafo[x][i].first;
		if(!marc2[viz]){
			altura[viz] = altura[x] + grafo[x][i].second;
			maxd = max(maxd, altura[viz]);
			dfs2(viz);
		}


	}

}
bool cmp(int a, int b){
	return a > b;
}
void dfs3(int x){
	marc3[x] = 1;
	
	for(int i = 0; i < grafo[x].size(); i++){
		int viz = grafo[x][i].first;
		if(!marc3[viz]){
			altura[viz] = altura[x] + grafo[x][i].second;
			maxd = max(maxd, altura[viz]);
			dfs3(viz);
		}


	}

}
int ans = 0;


int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	n = N, m = M, l = L;
	
	for(int i = 0; i < m; i++){
		//int a, b, t;
		//scanf("%d %d", &a, &b, &t);
		grafo[A[i]].push_back(make_pair(B[i], T[i]));
		grafo[B[i]].push_back(make_pair(A[i], T[i]));

	}
		//printf("%d\n", n);
	for(int i = 0; i < n; i++){
	
		if(!marc1[i]){
			maxd = 0;

			dfs1(i);
			altura[maxdi] = 0;
			maxd = 0;
			dfs2(maxdi);
			int centrodesse = 1e9 + 7, cdi;
			for(int j = 0; j < comp[qtdcomp].size(); j++){
				if(abs(altura[comp[qtdcomp][j]] - maxd/2) <=  centrodesse){
					cdi = comp[qtdcomp][j];
					centrodesse = abs(altura[comp[qtdcomp][j]] - maxd/2);
				}
			}
			centro[qtdcomp] = cdi;
			ans = max(maxd, ans);
			maxd = 0;
			altura[cdi] = 0;
			dfs3(cdi);

			maxraio[qtdcomp] = maxd;

			qtdcomp++;
		}



	}
	
	sort(maxraio, maxraio + qtdcomp, cmp);
	//printf("%d\n", maxraio[cfi]);
	if(qtdcomp > 1){
		ans = max(ans, maxraio[0] + maxraio[1] + l);
		if(qtdcomp > 2){
			ans = max(ans, maxraio[1] + maxraio[2] + 2*l);
		}
	}
	if(n == 1) return 0;
    return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int)':
dreaming.cpp:16:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[x].size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs2(int)':
dreaming.cpp:34:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[x].size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs3(int)':
dreaming.cpp:52:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < grafo[x].size(); i++){
                 ~~^~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:88:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int j = 0; j < comp[qtdcomp].size(); j++){
                   ~~^~~~~~~~~~~~~~~~~~~~~~
dreaming.cpp:94:20: warning: 'cdi' may be used uninitialized in this function [-Wmaybe-uninitialized]
    centro[qtdcomp] = cdi;
    ~~~~~~~~~~~~~~~~^~~~~

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