Submission #417930

#	Time	Username	Problem	Language	Result	Execution time	Memory
417930		T0p_	Dreaming (IOI13_dreaming)	C++14	100 / 100	144 ms	18728 KiB

dreaming

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

int pa[100100], mx1[100100], mx2[100100], dpn[100100], dpc[100100], rtc[100100];
vector<pair<int, int>> g[100100];
bool visit[100100];

int fp(int u)
{
	return (u == pa[u]) ? u : pa[u] = fp(pa[u]);
}

void dfs(int u)
{
	visit[u] = true;
	for(auto x : g[u])
	{
		if(visit[x.first]) continue;
		dfs(x.first);
		if(mx1[x.first] + x.second >= mx1[u])
		{
			mx2[u] = mx1[u];
			mx1[u] = mx1[x.first] + x.second;
		}
		else if(mx1[x.first] + x.second > mx2[u])
		{
			mx2[u] = mx1[x.first] + x.second;
		}
	}
}

void compute(int u, int p, int w)
{
	dpn[u] = max(w, mx1[u]);
	if(dpc[fp(u)] > dpn[u])
	{
		dpc[fp(u)] = dpn[u];
		rtc[fp(u)] = u;
	}

	for(auto x : g[u])
	{
		if(x.first == p) continue;
		int ww = w + x.second;
		if(mx1[x.first] + x.second == mx1[u]) ww = max(ww, mx2[u]+x.second);
		else ww = max(ww, mx1[u]+x.second);
		compute(x.first, u, ww);
	}
}

int solve(int N)
{
	for(int i=0 ; i<N ; i++)
	{
		visit[i] = false;
		pa[i] = i;
		mx1[i] = mx2[i] = dpn[i] = 0;
	}
	dfs(0);
	compute(0, -1, 0);
	int ret = 0;
	for(int i=0 ; i<N ; i++)
		ret = max(ret, dpn[i]);
	return ret;
}

int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
	for(int i=0 ; i<N ; i++)
	{
		pa[i] = i;
		dpc[i] = 1e9;
	}

	for(int i=0 ; i<M ; i++)
	{
		g[A[i]].push_back({B[i], T[i]});
		g[B[i]].push_back({A[i], T[i]});
		pa[fp(A[i])] = fp(B[i]);
	}

	for(int i=0 ; i<N ; i++)
	{
		if(visit[i]) continue;
		dfs(i);
		compute(i, -1, 0);
	}

	int mx = 0, root = 0;
	for(int i=0 ; i<N ; i++)
	{
		if(dpc[fp(i)] > mx)
		{
			mx = dpc[fp(i)];
			root = rtc[fp(i)];
		}
	}
	for(int i=0 ; i<N ; i++)
	{
		if(rtc[fp(i)] == root || !visit[fp(i)]) continue;
		visit[fp(i)] = false;
		g[root].push_back({rtc[fp(i)], L});
		g[rtc[fp(i)]].push_back({root, L});
	}
    return solve(N);
}

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