Submission #61264

#	Time	Username	Problem	Language	Result	Execution time	Memory
61264		Eae02	Dreaming (IOI13_dreaming)	C++14	100 / 100	155 ms	16124 KiB

dreaming

#include "dreaming.h"

#include <bits/stdc++.h>

struct Edge
{
	int len;
	struct Node* next;
};

struct Node
{
	std::vector<Edge> edges;
	int diamEdge;
	int component = -1;
};

void initComponent(Node* node)
{
	for (const Edge& e : node->edges)
	{
		if (e.next->component != -1)
			continue;
		e.next->component = node->component;
		initComponent(e.next);
	}
}

std::pair<Node*, int> furthestNode(Node* node, Node* prev)
{
	std::pair<Node*, int> furthest(node, 0);
	for (int i = 0; i < node->edges.size(); i++)
	{
		if (node->edges[i].next == prev)
			continue;
		auto c = furthestNode(node->edges[i].next, node);
		c.second += node->edges[i].len;
		if (c.second > furthest.second)
		{
			node->diamEdge = i;
			furthest = c;
		}
	}
	return furthest;
}

int travelTime(int numNodes, int numEdges, int newEdgeLen, int A[], int B[], int T[])
{
	std::vector<Node> nodes(numNodes);
	
	for (int i = 0; i < numEdges; i++)
	{
		int n1 = A[i];
		int n2 = B[i];
		nodes[n1].edges.push_back(Edge { T[i], &nodes[n2] });
		nodes[n2].edges.push_back(Edge { T[i], &nodes[n1] });
	}
	
	struct Comp
	{
		Node* mid;
		int depth;
		
		inline bool operator<(const Comp& other) const
		{
			return depth > other.depth;
		}
	};
	
	std::vector<Comp> componentInfo;
	
	int numComponents = 0;
	int maxDiameter = 0;
	for (int i = 0; i < numNodes; i++)
	{
		if (nodes[i].component != -1)
			continue;
		nodes[i].component = numComponents++;
		initComponent(&nodes[i]);
		
		auto f1 = furthestNode(&nodes[i], nullptr);
		auto f2 = furthestNode(f1.first, nullptr);
		
		int diameter = f2.second;
		maxDiameter = std::max(maxDiameter, diameter);
		
		Node* n = f1.first;
		int d = 0;
		int val = 0;
		while (d < diameter)
		{
			int nextD = d + n->edges[n->diamEdge].len;
			Node* nextN = n->edges[n->diamEdge].next;
			
			val = std::max(d, diameter - d);
			int nextVal = std::max(nextD, diameter - nextD);
			
			if (val < nextVal)
				break;
			
			d = nextD;
			n = nextN;
		}
		
		componentInfo.push_back(Comp { n, val });
	}
	
	if (numComponents == 1)
		return maxDiameter;
	
	std::sort(componentInfo.begin(), componentInfo.end());
	
	int maxDist = maxDiameter;
	maxDist = std::max(maxDist, componentInfo[0].depth + componentInfo[1].depth + newEdgeLen);
	if (numComponents > 2)
		maxDist = std::max(maxDist, componentInfo[1].depth + componentInfo[2].depth + newEdgeLen * 2);
	
	return maxDist;
}

Compilation message (stderr)

dreaming.cpp: In function 'std::pair<Node*, int> furthestNode(Node*, Node*)':
dreaming.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < node->edges.size(); i++)
                  ~~^~~~~~~~~~~~~~~~~~~~

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