oj.uz

Submission #492003

# Submission time Handle Problem Language Result Execution time Memory
492003 2021-12-05T10:09:32 Z franfill Dreaming (IOI13_dreaming) C++17
0 / 100
 47 ms 12584 KB 
#include<bits/stdc++.h>
#include "dreaming.h"
using namespace std;
typedef long long ll;
typedef pair < ll , ll > pll;

vector < vector < pll > > g;
vector < bool > vis;
vector < pll > b;
ll d = 0;

ll dfs1(ll x, ll pa=-1)
{
	vis[x] = true;
	b[x] = {0, 0};
	for (auto [y, w] : g[x]) if (y != pa)
	{
		ll temp = dfs1(y, x) + w;
		if (b[x].second < temp) b[x].second = temp;
		if (b[x].first < b[x].second) swap(b[x].first, b[x].second); 
	}
	return b[x].first;
}

ll dfs2(ll x, ll w = 0, ll pa=-1)
{
	if (pa != -1)
	{
		ll up = b[pa].first;
		if (up == b[x].first + w) up = b[pa].second;
		up += w;

		if (up > b[x].second) b[x].second = up;
		if (b[x].second > b[x].first) swap(b[x].second, b[x].first);
	}
	ll bes = b[x].first;
	d = max(d, b[x].first + b[x].second);
	for (auto [y, w] : g[x]) if (y != pa)
	{
		bes = min(bes, dfs2(y, w, x));
	}
	return bes;
}

ll calc(ll x)
{
	dfs1(x);
	return dfs2(x);
}

int travelTime(int N, int M, int L, int A[], int B[], int T[]) 
{
	g.resize(N);	
	vis.resize(N, false);
	b.resize(N, {0, 0});
	for (ll i = 0; i < M; i++)
	{
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
	}
	ll g1=-1, g2=-1, g3=-1;
	for (ll x = 0; x < N; x++) if (!vis[x])
	{
		ll temp = calc(x);
		if (temp > g1)
		{
			g3 = g2;
			g2 = g1;
			g1 = temp;
		}
		else if (temp > g2)
		{
			g3 = g2;
			g2 = temp;
		}
		else if (temp > g3)
		{
			g3 = temp;
		}
	}
	if (g2 == -1)
	{
        assert(false);
		return d;
	}
	if (g3 == -1)
	{
		return g1 + g2 + L;
	}
	assert(false);
	ll ans = g1 + g2 + L;
	ans = max(ans, g2 + g3 + L + L);
	return ans;
}

Subtask #1
0 / 14.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 22 ms 12584 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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