제출 #158109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
158109		faremy	Training (IOI07_training)	C++14	30 / 100	4 ms	632 KiB

training

#include <iostream>
#include <algorithm>
#include <vector>


struct Edge
{
	Edge(int s, int e, int c) : start(s), end(e), cost(c) {}
	int start, end, cost;
};

const int MAXN = 1e3;

std::vector<int> spanningTree[MAXN];
std::vector<Edge> canRemove;
std::vector<Edge> graph[MAXN];

int depth[MAXN];
int sum[MAXN];
int dp[MAXN];


void calcdepth(int node)
{
	for (int child : spanningTree[node])
		if (depth[child] == -1)
		{
			depth[child] = depth[node] + 1;
			calcdepth(child);
		}
}

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(nullptr);
	std::cin.tie(nullptr);

	int nodes, edges;
	std::cin >> nodes >> edges;

	for (int iEdge = 0; iEdge < edges; iEdge++)
	{
		int start, end, cost;
		std::cin >> start >> end >> cost;
		start--; end--;

		if (cost == 0)
		{
			spanningTree[start].emplace_back(end);
			spanningTree[end].emplace_back(start);
		}
		else
		{
			canRemove.emplace_back(start, end, cost);
		}
	}

	int root = 0;
	while (spanningTree[root].size() == 2)
		root++;
	
	std::fill_n(depth, nodes, -1);
	depth[root] = 0;
	calcdepth(root);

	int obligCost = 0;
	for (Edge &edge : canRemove)
	{
		if (depth[edge.start] < depth[edge.end])
			std::swap(edge.start, edge.end);
		if ((depth[edge.start] - depth[edge.end]) % 2 == 1)
			obligCost += edge.cost;
		else
		{
			sum[depth[edge.start]] += edge.cost;
			graph[depth[edge.start]].emplace_back(-1, depth[edge.end], edge.cost);
		}
	}

	for (int iDepth = 1; iDepth < nodes; iDepth++)
	{
		dp[iDepth] = sum[iDepth] + dp[iDepth - 1];
		sum[iDepth] += sum[iDepth - 1];

		for (Edge &edge : graph[iDepth])
			dp[iDepth] = std::min(dp[iDepth], dp[edge.end] + sum[iDepth] - sum[edge.end] - edge.cost);
	}

	std::cout << obligCost + dp[nodes - 1] << '\n';

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9