Submission #846594

#	Time	Username	Problem	Language	Result	Execution time	Memory
846594		siewjh	Dreaming (IOI13_dreaming)	C++17	100 / 100	82 ms	25160 KiB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<pair<int, int>> adj[MAXN], cdist[MAXN];
bool pro[MAXN];
int dia, mxd;

int dfs(int x, int par){
	pro[x] = 1;
	for (auto nxt : adj[x]){
		int nn, nd; tie(nn, nd) = nxt;
		if (nn == par) continue;
		cdist[x].push_back({nd + dfs(nn, x), nn});
	}
	for (int i = 0; i < 2; i++) cdist[x].push_back({0, -1});
	sort(cdist[x].begin(), cdist[x].end(), greater<pair<int, int>>());
	return cdist[x][0].first;
}

void dfs2(int x, int par, int pd){
	dia = max(dia, max(pd + cdist[x][0].first, cdist[x][0].first + cdist[x][1].first));
	mxd = min(mxd, max(pd, cdist[x][0].first));
	for (auto nxt : adj[x]){
		int nn, nd; tie(nn, nd) = nxt;
		if (nn == par) continue;
		if (nn == cdist[x][0].second) dfs2(nn, x, max(pd, cdist[x][1].first) + nd);
		else dfs2(nn, x, max(pd, cdist[x][0].first) + nd);
	}
}

int travelTime(int nodes, int edges, int L, int A[], int B[], int T[]) {
    for (int i = 0; i < edges; i++){
		int a = A[i], b = B[i], c = T[i];
		adj[a].push_back({b, c});
		adj[b].push_back({a, c});
	}
	int ans = 0; vector<int> mxdvec;
	for (int i = 0; i < nodes; i++)
		if (!pro[i]){
			dia = 0, mxd = 2e9;
			dfs(i, -1); dfs2(i, -1, 0);
			ans = max(ans, dia);
			mxdvec.push_back(mxd);
		}
	sort(mxdvec.begin(), mxdvec.end(), greater<int>());
	if (mxdvec.size() >= 2) ans = max(ans, mxdvec[0] + mxdvec[1] + L);
	if (mxdvec.size() >= 3) ans = max(ans, mxdvec[1] + mxdvec[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