Submission #64940

#	Time	Username	Problem	Language	Result	Execution time	Memory
64940		gnoor	Dreaming (IOI13_dreaming)	C++17	100 / 100	134 ms	14072 KiB

dreaming

#include "dreaming.h"

#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int cen;

int ans=0;

struct ei {
	int vec,wgt;
};

vector<ei> pth[100100];
bool visit[100100];
int mx[100100];
int smx[100100];

int survey(int x,int p) {
	visit[x]=true;
	int cur;
	for (auto &i:pth[x]) {
		if (i.vec==p) continue;
		cur=i.wgt+survey(i.vec,x);
		if (cur>=mx[x]) {
			smx[x]=mx[x];
			mx[x]=cur;
		} else if (cur>smx[x]) {
			smx[x]=cur;
		}
	}
	return mx[x];
}

void findcen(int x,int p,int dis) {
	if (dis>=mx[x]) {
		smx[x]=mx[x];
		mx[x]=dis;
	} else if (dis>smx[x]) {
		smx[x]=dis;
	}
	ans=max(ans,smx[x]+mx[x]);
	cen=min(cen,mx[x]);

	for (auto &i:pth[x]) {
		if (i.vec==p) continue;
		if (i.wgt+mx[i.vec]==mx[x]) {
			findcen(i.vec,x,smx[x]+i.wgt);
		} else {
			findcen(i.vec,x,mx[x]+i.wgt);
		}
	}
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i=0;i<M;i++) {
		pth[A[i]].push_back(ei{B[i],T[i]});
		pth[B[i]].push_back(ei{A[i],T[i]});
	}
	vector<int> cens;
	for (int i=0;i<N;i++) {
		if (visit[i]) continue;
		survey(i,i);
		cen=1e9;
		findcen(i,i,0);
		cens.push_back(cen);
	}
	sort(cens.begin(),cens.end(),[](int &a, int &b) {
			return a>b;
			});
	if (cens.size()>1) ans=max(ans,cens[0]+cens[1]+L);
	if (cens.size()>2) ans=max(ans,cens[1]+cens[2]+2*L);
	return ans;
}

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