제출 #1268632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268632		cmiuc	꿈 (IOI13_dreaming)	C++20	100 / 100	42 ms	16412 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, Ans;

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);
	}
	Ans = max(Ans, Mx[u][3] + Mx[u][1]);
	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 Ans;
	if (m == n - 2)
		return max(Ans, M1 + M2 + l);
	return max(Ans, max(M1 + M2 + l, M2 + M3 + l + l));
}

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