Submission #99731

#	Time	Username	Problem	Language	Result	Execution time	Memory
99731		Retro3014	Dreaming (IOI13_dreaming)	C++17	100 / 100	120 ms	12408 KiB

dreaming

#include "dreaming.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

#define MAX_N 100000

struct S{
	int x, y;
};

vector<S> gp[MAX_N+1];
int ans = 0;
bool vst[MAX_N+1];
vector<int> v;


int k1, k2;
bool vst11[MAX_N+1], vst12[MAX_N+1];
void dfs11(int x, int y){
	vst11[x] = true;
	if(k1<y){
		k1 = y; k2 = x;
	}
	for(int i=0; i<gp[x].size(); i++){
		if(!vst11[gp[x][i].x])	dfs11(gp[x][i].x, y+gp[x][i].y);
	}
}
void dfs12(int x, int y){
	vst12[x] = true;
	if(k1<y){
		k1 = y; k2 = x;
	}
	for(int i=0; i<gp[x].size(); i++){
		if(!vst12[gp[x][i].x])	dfs12(gp[x][i].x, y+gp[x][i].y);
	}
}

int dist[MAX_N+1];
bool vst21[MAX_N+1];

void dfs21(int x){
	dist[x] = 0;
	vst21[x] = true;
	for(int i=0; i<gp[x].size(); i++){
		if(!vst21[gp[x][i].x]){
			dfs21(gp[x][i].x);
			dist[x] = max(dist[x], dist[gp[x][i].x]+gp[x][i].y);
		}
	}
	return;
}

bool vst22[MAX_N+1];

int dfs22(int x, int y){
	vst22[x] = true;
	int t1=0, t2=0, idx, t3;
	for(int i=0; i<gp[x].size(); i++){
		if(!vst22[gp[x][i].x]){
			if(t1<dist[gp[x][i].x] + gp[x][i].y){
				t2 = t1;
				t1 = dist[gp[x][i].x] + gp[x][i].y;
				t3 = gp[x][i].y;
				idx =  gp[x][i].x;
			}
			else if(t2<dist[gp[x][i].x] + gp[x][i].y){
				t2 = dist[gp[x][i].x] + gp[x][i].y;
			}
		}
	}
	if(t1==0){
		return y;
	}
	//cout<<x<<' '<<y<<' '<<t1<<' '<<t2<<' '<<t3<<endl;
	return min(max(y, t1), dfs22(idx, max(y, t2)+t3));
}

void dfs1(int x){
	k1 = 0; k2 = x;
	dfs11(x, 0);
	k1 = 0;
	dfs12(k2, 0);
	ans = max(ans, k1);
	dfs21(x);
	v.push_back(dfs22(x, 0));
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for(int i=0; i<M; i++){
		gp[A[i]].push_back({B[i], T[i]});
		gp[B[i]].push_back({A[i], T[i]});
	}
	for(int i=0; i<N; i++){
		if(!vst11[i]){
			dfs1(i);
		}
	}
	sort(v.begin(), v.end());
	/*for(int i=0; i<v.size(); i++){
		printf("%d ",v[i]);
	}*/
	if(v.size()>=2){
		ans = max(ans, v[v.size()-1]+v[v.size()-2]+L);
	}
	if(v.size()>=3){
		ans = max(ans, v[v.size()-2]+v[v.size()-3]+2*L);
	}
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs11(int, int)':
dreaming.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs12(int, int)':
dreaming.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
dreaming.cpp: In function 'void dfs21(int)':
dreaming.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].size(); i++){
               ~^~~~~~~~~~~~~
dreaming.cpp: In function 'int dfs22(int, int)':
dreaming.cpp:62:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<gp[x].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