Submission #915785

#	Time	Username	Problem	Language	Result	Execution time	Memory
915785		XXBabaProBerkay	Dreaming (IOI13_dreaming)	C++17	0 / 100	34 ms	9820 KiB

dreaming

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

#define F first
#define S second

using ll = long long;

const int INF = 1e9 + 7;
const int MOD = 998244353;

const int MAXN = 1e5;

int n;
int dp[MAXN + 1];
vector<vector<pair<int, int>>> adj;
 
int dfs(int k, int p)
{
	if (!dp[k])
	{
		dp[k] = 1;
		for (pair<int, int> i : adj[k])
			if (i.F != p)
				dp[k] += dfs(i.F, k);
 
		return dp[k];
	}
 
	int mx = 0;
	for (pair<int, int> i : adj[k])
	{
		if (i.F == p)
			continue;
		
		if (dp[i.F] > dp[mx])
			mx = i.F;
	}
 
	if (dp[mx] <= (n >> 1))
		return k;
 
	return dfs(mx, k);
}

int dfs2(int k, int p)
{
	int res = 0;
	for (pair<int, int> i : adj[k])
		if (i.F != p)
			res = max(res, i.S + dfs2(i.F, k));

	return res;
}

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

	vector<int> v;
	for (int i = 1; i <= N; i++)
		if (!dp[i])
		{
			dfs(i, i);
			n = dp[i];
			int x = dfs(i, i);
			v.push_back(dfs2(x, x));
		}

	sort(v.begin(), v.end(), greater<int>());

	return v[0] + v[1] + L;
}

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