oj.uz

Submission #158109

# Submission time Handle Problem Language Result Execution time Memory
158109 2019-10-14T19:09:25 Z faremy Training (IOI07_training) C++14
30 / 100
 4 ms 632 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 420 KB Output isn't correct

Subtask #5
0 / 9.0

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

Subtask #6
0 / 9.0

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

Subtask #7
0 / 9.0

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

Subtask #8
0 / 9.0

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

Subtask #9
0 / 9.0

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

Subtask #10
0 / 9.0

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

Subtask #11
0 / 9.0

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