제출 #61258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
61258		Eae02	꿈 (IOI13_dreaming)	C++14	18 / 100	70 ms	14328 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 diameter;
	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);
		
		diameter = f2.second;
		
		Node* n = f1.first;
		int halfDiam = std::round(diameter / 2.0);
		int d = 0;
		while (d < halfDiam)
		{
			d += n->edges[n->diamEdge].len;
			n = n->edges[n->diamEdge].next;
		}
		
		componentInfo.push_back(Comp { n, std::max(d, diameter - d) });
	}
	
	if (numComponents == 1)
		return diameter;
	
	std::sort(componentInfo.begin(), componentInfo.end());
	
	int maxDist = diameter;
	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;
}

컴파일 시 표준 에러 (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++)
                  ~~^~~~~~~~~~~~~~~~~~~~
dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:73:6: warning: 'diameter' may be used uninitialized in this function [-Wmaybe-uninitialized]
  int diameter;
      ^~~~~~~~

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