oj.uz

Submission #60013

# Submission time Handle Problem Language Result Execution time Memory
60013 2018-07-23T12:18:36 Z Eae02 Duathlon (APIO18_duathlon) C++14
0 / 100
 248 ms 19328 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;
		
		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 0 ms 248 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 20.0

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

Subtask #8
0 / 8.0

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

Subtask #9
0 / 10.0

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