Submission #492056

#	Time	Username	Problem	Language	Result	Execution time	Memory
492056		nick_kcin	Dreaming (IOI13_dreaming)	C++14	0 / 100	1092 ms	19676 KiB

dreaming

#include "dreaming.h"
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define MAXN ((int)1e5 + 5)
#define INF ((int)1e9 + 5)

struct Node
{
	vector<int> ne;
	vector<int> nw;
	int treenum;
	int maxp;    // maximum path
};
int trnum;
Node g[MAXN];
bool marca[MAXN];

void dfs0(int n, int p)
{
	marca[n] = true;
	g[n].treenum = trnum;
	for (int nxt : g[n].ne)
		if (nxt != p)
			dfs0(nxt, n);
}

int trval[MAXN];
int trhead[MAXN];
void dfs1(int n, int p)
{
	if (g[n].ne.size() == 0)
	{
		trval[g[n].treenum] = 0;
		return;
	}

	if (p != -1 && g[n].ne.size() == 1)
	{
		g[n].maxp = 0;
		return;
	}

	int pmax = 0;
	for (int i = 0; i < g[n].ne.size(); i++)
	{
		int nxt = g[n].ne[i];
		if (nxt == p)
			continue;
		int nwe = g[n].nw[i];
		dfs1(nxt, n);
		pmax = max(pmax, nwe + g[nxt].maxp);
	}
	g[n].maxp = pmax;
}

map<int, int> trm;    // tree map, trval and trinx
int travelTime(int N, int M, int L, int A[], int B[], int T[])
{
	for (int i = 0; i < M; i++)
	{
		int a = A[i];
		int b = B[i];
		int w = T[i];
		g[a].ne.push_back(b);
		g[a].nw.push_back(w);
		g[b].ne.push_back(a);
		g[b].nw.push_back(w);
	}

	trnum = 0;
	for (int i = 0; i < N; i++)
	{
		if (!marca[i])
		{
			dfs0(i, -1);
			trnum++;
		}
	}

	fill(trval, trval + trnum, INF);
	for (int i = 0; i < N; i++)
	{
		int tn = g[i].treenum;
		dfs1(i, -1);
		if(g[i].maxp < trval[tn])
		{
			trval[tn] = g[i].maxp;
			trhead[tn] = T[i];
		}
	}

	// for (int i = 0; i < trnum; i++)
	// {
	// 	fprintf(stderr, "D: tr %d,  peso = %d\n", i, trval[i]);
	// }

	if (trnum == 1)
		return trval[0];
	else if (trnum == 2)
		return trval[0] + trval[1] + L;

	int ok = INF;
	for (int i = 0; i < trnum; i++)
	{
		trm[trval[i]] = i;
	}
	for (int i = 0; i < trnum; i++)
	{
		// i root
		trm.erase(trval[i]);
		auto it = trm.end();
		it--;
		int nvalr = it->first + trval[i] + L;
		int nval2 = it->first;
		it--;
		nval2 += it->first;
		nval2 += 2*L + trhead[i];
		ok = min(ok, max(nval2, nvalr));
		// fprintf(stderr, "WHEN root %d: r = %d, 2 = %d\n", i, nvalr, nval2);
		trm[trval[i]] = i;
	}

	return ok;
}

Compilation message (stderr)

dreaming.cpp: In function 'void dfs1(int, int)':
dreaming.cpp:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for (int i = 0; i < g[n].ne.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~

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