Submission #447655

#	Time	Username	Problem	Language	Result	Execution time	Memory
447655		antontsiorvas	Dreaming (IOI13_dreaming)	C++14	100 / 100	113 ms	17988 KiB

dreaming

#include "dreaming.h"
#include <cstdio>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

int cnt, root[100005], dpdown[100005][3], dpup[100005], maxdiam, minv[100005];
vector< pair<int, int> > adj[100005];
bool visited[100005];

void dfsdown(int v, int prev){
	visited[v] = true;
	
	for(int i=0; i<adj[v].size(); i++){
		int next = adj[v][i].first;
		int time = adj[v][i].second;
		if(next == prev) continue;
		dfsdown(next,v);
		int weight = dpdown[next][0] + time;
		if(dpdown[v][0] < weight){
			dpdown[v][1] = dpdown[v][0];
			dpdown[v][0] = weight;
			dpdown[v][2] = next;
		}
		else if(dpdown[v][1] < weight && weight < dpdown[v][0]) dpdown[v][1] = weight;
	}
	
}

void dfsup(int v, int prev, int w){
	dpup[v] = w;
	for(int i=0; i<adj[v].size(); i++){
		int next = adj[v][i].first;
		int time = adj[v][i].second;
		if(next == prev) continue;
		if(next == dpdown[v][2]) dfsup(next,v,max(dpdown[v][1],w)+time);
		else dfsup(next,v,max(dpdown[v][0],w)+time);
	}
}

void dfsfinal(int v, int prev){
	maxdiam = max(maxdiam,max(dpdown[v][0],dpup[v]));
	if(dpdown[v][0] != 0 && dpup[v] != 0) minv[cnt] = min(minv[cnt],max(dpup[v],dpdown[v][0]));
	else if(dpdown[v][0] != 0) minv[cnt] = min(minv[cnt],dpdown[v][0]);
	else if(dpup[v] != 0) minv[cnt] = min(minv[cnt],dpup[v]);
	for(int i=0; i<adj[v].size(); i++){
		int next = adj[v][i].first;
		if(next == prev) continue;
		dfsfinal(next,v);
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
    for(int i=0; i<M; i++){
    	adj[A[i]].push_back(make_pair(B[i],T[i]));
    	adj[B[i]].push_back(make_pair(A[i],T[i]));
	}
	for(int i=0; i<N; i++){
		if(!visited[i]){
			cnt++;
			root[cnt] = i;
			dfsdown(i,-1);
			dfsup(i,-1,0);
			minv[cnt] = dpdown[i][0];
			dfsfinal(i,-1);
		}
	}
//	for(int i=1; i<=cnt; i++) printf("%d ",minv[i]);
	sort(minv+1,minv+cnt+1);
//	for(int i=1; i<=cnt; i++) printf("%d ",minv[i]);
//	for(int i=0; i<N; i++) printf("%d) %d %d %d %d\n",i,dpdown[i][0],dpdown[i][1],dpdown[i][2],dpup[i]);
	if(cnt == 1) return maxdiam;
	if(cnt == 2) return max(maxdiam, minv[cnt]+minv[cnt-1]+L);
	return max(maxdiam, max(minv[cnt]+minv[cnt-1]+L,minv[cnt-1]+minv[cnt-2]+2*L));
//	for(int i=0; i<N; i++) printf("%d) %d %d %d %d\n",i,dpdown[i][0],dpdown[i][1],dpdown[i][2],dpup[i]);
	
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfsdown(int, int)':
dreaming.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i=0; i<adj[v].size(); i++){
      |               ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfsup(int, int, int)':
dreaming.cpp:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i=0; i<adj[v].size(); i++){
      |               ~^~~~~~~~~~~~~~
dreaming.cpp: In function 'void dfsfinal(int, int)':
dreaming.cpp:47:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i=0; i<adj[v].size(); i++){
      |               ~^~~~~~~~~~~~~~

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