제출 #1278992

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278992		IBory	꿈 (IOI13_dreaming)	C++20	100 / 100	97 ms	17128 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;

const int MAX = 100007;
int V[2][MAX], D[2][MAX];
vector<pii> G[MAX];
vector<int> C;

int DFS(int cur, int c) {
	int ret = cur;
	V[c][cur] = 1;
	for (auto [next, nd] : G[cur]) {
		if (V[c][next]) continue;
		D[c][next] = D[c][cur] + nd;
		int d = DFS(next, c);
		if (D[c][d] > D[c][ret]) ret = d;
	}
	return ret;
}

int travelTime(int N, int M, int L, int* A, int* B, int* T) {
	for (int i = 0; i < M; ++i) {
		G[A[i]].emplace_back(B[i], T[i]);
		G[B[i]].emplace_back(A[i], T[i]);
	}

	int rad = 0;
	memset(D, 0x3f, sizeof(D));
	for (int i = 0; i < N; ++i) {
		if (V[0][i]) continue;
		D[0][i] = 0;
		int d1 = DFS(i, 0);
		D[1][d1] = 0;
		int d2 = DFS(d1, 1);
		int hd = 2e9, d = D[1][d2];
		rad = max(d, rad);
		while (d2 != d1) {
			for (auto [prev, pd] : G[d2]) {
				if (D[1][prev] + pd != D[1][d2]) continue;
				d2 = prev;
				break;
			}
			hd = min(hd, max(D[1][d2], d - D[1][d2]));
		}
		hd = min(hd, d);
		C.push_back(hd);
	}

	sort(C.begin(), C.end(), greater<int>());
	if (C.size() == 1) return max(rad, C[0]);
	else if (C.size() == 2) return max(rad, C[0] + C[1] + L);
	return max({rad, C[0] + C[1] + L, C[1] + C[2] + L * 2});
}

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