Submission #762150

#	Time	Username	Problem	Language	Result	Execution time	Memory
762150		SanguineChameleon	Dreaming (IOI13_dreaming)	C++17	100 / 100	71 ms	21168 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
vector<pair<int, int>> adj[maxN];
bool flag[maxN];
pair<int, int> max1[maxN];
int max2[maxN];
int depth[maxN];

void dfs1(int u, int p) {
	flag[u] = true;
	max1[u] = make_pair(0, u);
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (v != p) {
			dfs1(v, u);
			max1[u] = max(max1[u], make_pair(max1[v].first + w, max1[v].second));
		}
	}
}

int dfs2(int u, int p) {
	max2[u] = max(max2[u], depth[u]);
	int res = max2[u];
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (v != p) {
			depth[v] = depth[u] + w;
			res = min(res, dfs2(v, u));
		}
	}
	return res;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i = 0; i < M; i++) {
		adj[A[i]].emplace_back(B[i], T[i]);
		adj[B[i]].emplace_back(A[i], T[i]);
	}
	int res = 0;
	vector<int> mins;
	for (int i = 0; i < N; i++) {
		if (flag[i]) {
			continue;
		}
		dfs1(i, -1);
		int x = max1[i].second;
		dfs1(x, -1);
		int y = max1[x].second;
		res = max(res, max1[x].first);
		depth[x] = 0;
		dfs2(x, -1);
		depth[y] = 0;
		mins.push_back(dfs2(y, -1));
	}
	sort(mins.begin(), mins.end(), greater<>());
	if ((int)mins.size() >= 2) {
		res = max(res, mins[0] + mins[1] + L);
	}
	if ((int)mins.size() >= 3) {
		res = max(res, mins[1] + mins[2] + L * 2);
	}
	return res;
}

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