Submission #60013

#	Time	Username	Problem	Language	Result	Execution time	Memory
60013		Eae02	Duathlon (APIO18_duathlon)	C++14	0 / 100	248 ms	19328 KiB

count_triplets

#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
• Subtask 2: 0 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 10
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 20
• Subtask 8: 0 / 8
• Subtask 9: 0 / 10