Submission #158259

#	Time	Username	Problem	Language	Result	Execution time	Memory
158259		faremy	Training (IOI07_training)	C++14	100 / 100	18 ms	5140 KiB

training

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