Submission #172308

#	Time	Username	Problem	Language	Result	Execution time	Memory
172308		maruii	Dreaming (IOI13_dreaming)	C++14	100 / 100	117 ms	17272 KiB

dreaming

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

vector<pii> edge[100005];
int par[100005], X[100005];
bool vis[100005];

pii dfs(int x, int p) {
	pii ret = {0, x};
	for (auto i : edge[x]) {
		if (i.ss == p) continue;
		auto t = dfs(i.ss, x);
		ret = max(ret, pii(t.ff + i.ff, t.ss));
	}
	X[x] = ret.ff;
	par[x] = p;
	vis[x] = 1;
	return ret;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) {
	for (int i = 0; i < M; ++i) {
		edge[A[i]].emplace_back(T[i], B[i]);
		edge[B[i]].emplace_back(T[i], A[i]);
	}
	vector<int> vec;
	int ans, dia = 0;
	for (int i = 0; i < N; ++i) {
		if (vis[i]) continue;
		auto t = dfs(dfs(i, i).ss, -1);
		int x = t.ss, mn = t.ff;
		for (; x >= 0; x = par[x]) mn = min(mn, max(X[x], t.ff - X[x]));
		vec.push_back(mn);
		dia = max(dia, t.ff);
	}
	sort(vec.rbegin(), vec.rend());
	if (vec.size() > 2) {
		ans = L + vec[0] + vec[1];
		for (int i = 2; i < vec.size(); ++i) ans = max(ans, L + L + vec[1] + vec[i]);
	}
	else if (vec.size() == 2) ans = L + vec[0] + vec[1];
	else ans = 0;
	ans = max(ans, dia);
	return ans;
}

Compilation message (stderr)

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 2; i < vec.size(); ++i) ans = max(ans, L + L + vec[1] + vec[i]);
                   ~~^~~~~~~~~~~~

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