Submission #218878

#	Time	Username	Problem	Language	Result	Execution time	Memory
218878		bigg	Dreaming (IOI13_dreaming)	C++14	100 / 100	144 ms	18292 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, mind;

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;
			if(altura[viz] >= maxd){
				maxd = altura[viz];
				maxdi = viz;
			};
			dfs2(viz);
		}


	}

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


	}

}
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;
			int a = maxdi;

			dfs2(maxdi);
			int b = maxdi;
			int centrodesse = 1e9 + 7, cdi;
			mind = -1;
			
			dfs3(a, 0, 1);
			dfs3(b, 0 ,2);
			
			ans = max(ans, maxd);

			maxraio[qtdcomp] = mind;
			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);
		}
	}

    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, int, int)':
dreaming.cpp:62: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:100:8: warning: unused variable 'centrodesse' [-Wunused-variable]
    int centrodesse = 1e9 + 7, cdi;
        ^~~~~~~~~~~
dreaming.cpp:100:31: warning: unused variable 'cdi' [-Wunused-variable]
    int centrodesse = 1e9 + 7, cdi;
                               ^~~

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