oj.uz

Submission #60017

# Submission time Handle Problem Language Result Execution time Memory
60017 2018-07-23T12:23:09 Z Eae02 Duathlon (APIO18_duathlon) C++14
10 / 100
 1000 ms 19376 KB 
#include <bits/stdc++.h>

struct Node
{
	std::vector<int> connected;
	std::vector<int> children;
	int totalChildren;
	bool visited = false;
};

std::vector<Node> nodes;

int genTree(int i)
{
	nodes[i].totalChildren = 0;
	for (int c : nodes[i].connected)
	{
		if (!nodes[c].children.empty())
			continue;
		nodes[i].children.push_back(c);
		nodes[i].totalChildren += genTree(c);
	}
	return nodes[i].totalChildren + 1;
}

uint64_t memo[100000][2];

uint64_t count(int n, bool placedM)
{
	uint64_t& m = memo[n][placedM ? 1 : 0];
	if (m != 0)
		return m - 1;
	
	nodes[n].visited = true;
	
	uint64_t x = placedM ? 1 : 0;
	for (int i : nodes[n].connected)
	{
		if (nodes[i].visited)
			continue;
		if (!placedM)
			x += count(i, false);
		x += count(i, true);
	}
	
	nodes[n].visited = false;
	m = x + 1;
	return x;
}

int main()
{
	int numNodes, numEdges;
	std::cin >> numNodes;
	std::cin >> numEdges;
	
	nodes.resize(numNodes);
	for (int i = 0; i < numEdges; i++)
	{
		int a, b;
		std::cin >> a;
		std::cin >> b;
		a--;
		b--;
		
		nodes[a].connected.push_back(b);
		nodes[b].connected.push_back(a);
	}
	
	uint64_t x = 0;
	for (int i = 0; i < numNodes; i++)
	{
		nodes[i].visited = true;
		
		std::memset(memo, 0, sizeof(memo));
		for (int c : nodes[i].connected)
		{
			x += count(c, false);
		}
		
		nodes[i].visited = false;
	}
	
	std::cout << x << std::endl;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 19376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 19376 KB Output is correct
2 Correct 158 ms 19376 KB Output is correct
3 Correct 139 ms 19376 KB Output is correct
4 Correct 149 ms 19376 KB Output is correct
5 Correct 155 ms 19376 KB Output is correct
6 Correct 146 ms 19376 KB Output is correct
7 Correct 149 ms 19376 KB Output is correct
8 Correct 154 ms 19376 KB Output is correct
9 Correct 164 ms 19376 KB Output is correct
10 Correct 129 ms 19376 KB Output is correct
11 Correct 135 ms 19376 KB Output is correct
12 Correct 129 ms 19376 KB Output is correct
13 Correct 111 ms 19376 KB Output is correct
14 Correct 103 ms 19376 KB Output is correct
15 Correct 111 ms 19376 KB Output is correct
16 Correct 106 ms 19376 KB Output is correct
17 Correct 108 ms 19376 KB Output is correct
18 Correct 133 ms 19376 KB Output is correct
19 Correct 126 ms 19376 KB Output is correct
20 Correct 118 ms 19376 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 19376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 19376 KB Output is correct
2 Correct 174 ms 19376 KB Output is correct
3 Incorrect 165 ms 19376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1029 ms 19376 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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