oj.uz

Submission #158259

# Submission time Handle Problem Language Result Execution time Memory
158259 2019-10-15T20:12:34 Z faremy Training (IOI07_training) C++14
100 / 100
 18 ms 5140 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>


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

const int MAXN = 1e3;
const int MAXM = 1 << 10;
const int MAXD = 10;
const int INFTY = 1e9;

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

int depth[MAXN];
int parent[MAXN];
int parSt[MAXN];
int strees[MAXN];
int chd[MAXN][MAXD + 1];

std::vector<Edge> graph[MAXN];
int dp[MAXN][MAXD + 1];
int trans[MAXN][MAXD][MAXD + 1];
int bitdp[MAXN][MAXM];


void calcdepth(int node)
{
	for (int child : spanningTree[node])
		if (child != parent[node])
		{
			depth[child] = depth[node] + 1;
			parent[child] = node;
			chd[node][strees[node]] = child;
			parSt[child] = strees[node]++;
			calcdepth(child);
		}
}

int lca(int u, int v)
{
	while (depth[u] > depth[v])
		u = parent[u];
	while (depth[u] < depth[v])
		v = parent[v];
	while (u != v)
	{
		u = parent[u];
	   	v = parent[v];
	}

	return u;
}

std::pair<int, int> getw(int node, int stop, int from)
{
	int offset = 0;
	if (from != MAXD)
		offset = dp[chd[node][from]][MAXD];

	if (node == stop)
		return { -offset, from };
	std::pair<int, int> w = getw(parent[node], stop, parSt[node]);
	return { w.first + dp[node][from] - offset, w.second };
}

void compute(int node)
{
	bitdp[node][0] = 0;
	for (int child : spanningTree[node])
		if (child != parent[node])
		{
			compute(child);
			bitdp[node][0] += dp[child][MAXD];
		}

	for (Edge &edge : graph[node])
	{
		std::pair<int, int> left = getw(edge.start, node, MAXD);
		std::pair<int, int> right = getw(edge.end, node, MAXD);

		int froml = std::min(left.second, right.second);
		int fromr = std::max(left.second, right.second);
		trans[node][froml][fromr] = std::min(trans[node][froml][fromr], left.first + right.first - edge.cost);
		bitdp[node][0] += edge.cost;
	}

	int masks = 1 << strees[node];
	for (int iMask = 1; iMask < masks; iMask++)
	{
		int last = 31 - __builtin_clz(iMask);
		bitdp[node][iMask] = std::min(bitdp[node][iMask], bitdp[node][iMask ^ (1 << last)] + trans[node][last][MAXD]);

		for (int iBit = 0; iBit < last; iBit++)
			if ((iMask >> iBit) & 1)
				bitdp[node][iMask] = std::min(bitdp[node][iMask], bitdp[node][iMask ^ (1 << last) ^ (1 << iBit)] + trans[node][iBit][last]);
	}

	for (int iTree = 0; iTree < strees[node]; iTree++)
		for (int iMask = 0; iMask < masks; iMask++)
			if (((iMask >> iTree) & 1) == 0)
				dp[node][iTree] = std::min(dp[node][iTree], bitdp[node][iMask]);

	for (int iMask = 0; iMask < masks; iMask++)
		dp[node][MAXD] = std::min(dp[node][MAXD], bitdp[node][iMask]);
}

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);
		}
	}

	calcdepth(0);
	std::fill_n((int *)dp, MAXN * (MAXD + 1), INFTY);
	std::fill_n((int *)trans, MAXN * MAXD * (MAXD + 1), INFTY);
	std::fill_n((int *)bitdp, MAXN * MAXM, INFTY);

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

	compute(0);
	std::cout << obligCost + dp[0][MAXD] << '\n';

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4860 KB Output is correct
2 Correct 6 ms 4856 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4856 KB Output is correct
2 Correct 6 ms 4860 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4860 KB Output is correct
2 Correct 6 ms 4856 KB Output is correct

Subtask #7
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4856 KB Output is correct
2 Correct 7 ms 4984 KB Output is correct

Subtask #8
9.0 / 9.0

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

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5112 KB Output is correct
2 Correct 9 ms 5112 KB Output is correct
3 Correct 8 ms 5096 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5068 KB Output is correct
2 Correct 8 ms 4984 KB Output is correct
3 Correct 16 ms 5140 KB Output is correct
4 Correct 9 ms 4984 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5112 KB Output is correct
2 Correct 18 ms 5116 KB Output is correct
3 Correct 12 ms 5112 KB Output is correct
4 Correct 9 ms 5112 KB Output is correct