oj.uz

Submission #61261

# Submission time Handle Problem Language Result Execution time Memory
61261 2018-07-25T14:26:33 Z Eae02 Dreaming (IOI13_dreaming) C++14
18 / 100
 76 ms 14328 KB 
#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 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 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;
}

Compilation message

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.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 23.0

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

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 6788 KB Output is correct
2 Correct 30 ms 6780 KB Output is correct
3 Correct 33 ms 6676 KB Output is correct
4 Correct 28 ms 6780 KB Output is correct
5 Correct 28 ms 6780 KB Output is correct
6 Correct 34 ms 8056 KB Output is correct
7 Correct 29 ms 7036 KB Output is correct
8 Correct 30 ms 6652 KB Output is correct
9 Correct 31 ms 6640 KB Output is correct
10 Correct 38 ms 7032 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 9 ms 5748 KB Output is correct
13 Correct 10 ms 5748 KB Output is correct
14 Correct 10 ms 5620 KB Output is correct
15 Correct 9 ms 5620 KB Output is correct
16 Correct 9 ms 5620 KB Output is correct
17 Correct 9 ms 5620 KB Output is correct
18 Correct 9 ms 5748 KB Output is correct
19 Correct 9 ms 5748 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 3 ms 512 KB Output is correct
23 Correct 9 ms 5748 KB Output is correct

Subtask #5
0 / 12.0

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

Subtask #6
0 / 23.0

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