oj.uz

Submission #915785

# Submission time Handle Problem Language Result Execution time Memory
915785 2024-01-24T17:19:13 Z XXBabaProBerkay Dreaming (IOI13_dreaming) C++17
0 / 100
 34 ms 9820 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 5720 KB Output is correct
2 Incorrect 16 ms 5720 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 9820 KB Output isn't correct
2 Halted 0 ms 0 KB -