Submission #1268629

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268629		cmiuc	Dreaming (IOI13_dreaming)	C++20	0 / 100	28 ms	11840 KiB

dreaming

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

using namespace std;
const int N = 1e5 + 10;
vector<pair<int,int>> nei[N];
int Mx[N][4], Min;

void dfs2(int u, int p){
	for (auto [i, w] : nei[u]){
		if (i == p)
			continue;
		if (Mx[i][1] + w == Mx[u][1])
			Mx[i][3] = max(Mx[u][3], Mx[u][2]) + w;
		else
			Mx[i][3] = max(Mx[u][3], Mx[u][1]) + w;
		dfs2(i, u);
	}
	Min = min(Min, max(Mx[u][3], Mx[u][1]));
}

void dfs1(int u, int p){
	for (auto [i, w] : nei[u]){
		if (i == p)
			continue;
		dfs1(i, u);
		if (Mx[i][1] + w > Mx[u][1])
			Mx[u][2] = Mx[u][1], Mx[u][1] = Mx[i][1] + w;
		else
			Mx[u][2] = max(Mx[u][2], Mx[i][1] + w);
	}
}

int travelTime(int n, int m, int l, int A[], int B[], int T[]){
	for (int i=0;i<m;i++){
		nei[B[i]].push_back({A[i], T[i]});
		nei[A[i]].push_back({B[i], T[i]});
	}

	int M1 = 0, M2 = 0, M3 = 0;
	for (int i=0;i<n;i++){
		if (Mx[i][1] or Mx[i][3])
			continue;
		Min = 1e9;
		dfs1(i, i);
		dfs2(i, i);
		if (Min > M1)
			M3 = M2, M2 = M1, M1 = Min;
		else if (Min > M2)
			M3 = M2, M2 = Min;
		else
			M3 = max(M3, Min);
	}

	if (m == n - 1)
		return M1;
	return max(M1 + M2 + l, M2 + M3 + l + l);
}

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