Submission #297142

#	Time	Username	Problem	Language	Result	Execution time	Memory
297142		Kastanda	Training (IOI07_training)	C++11	100 / 100	87 ms	4736 KiB

training

// M
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1005, MXM = N * 5;
int n, m, P[N], H[N], A[MXM], B[MXM], C[MXM], rev[N];
vector < int > Ch[N];
ll F[N], dp[N][1 << 10];
vector < vector < int > > V1[N], V2[N];
void DFS(int v, int p)
{
	P[v] = p;
	for (int i = 0; i < (int)Ch[v].size(); i ++)
		if (Ch[v][i] == p)
			Ch[v].erase(Ch[v].begin() + i);
	for (int u : Ch[v])
		H[u] = H[v] + 1, DFS(u, v);
}
void Add(int v, ll val)
{
	F[v] += val;
	for (int u : Ch[v])
		Add(u, val);
}
void DFS2(int v)
{
	for (int u : Ch[v])
		DFS2(u);
	int d = (int)Ch[v].size();
	for (int i = 0; i < d; i ++)
		rev[Ch[v][i]] = i;
	for (int mask = 1; mask < (1 << d); mask ++)
	{
		for (int i = 0; i < d; i ++)
			if (mask >> i & 1)
				dp[v][mask] += dp[Ch[v][i]][(1 << (int)Ch[Ch[v][i]].size()) - 1];
		for (auto vec : V1[v])
			if (mask >> rev[vec[2]] & 1)
				dp[v][mask] = max(dp[v][mask], dp[v][mask - (1 << rev[vec[2]])] + F[vec[1]] + C[vec[0]]);
		for (auto vec : V2[v])
			if ((mask >> rev[vec[3]] & 1) && (mask >> rev[vec[4]] & 1))
				dp[v][mask] = max(dp[v][mask], dp[v][mask - (1 << rev[vec[3]]) - (1 << rev[vec[4]])] + F[vec[1]] + F[vec[2]] + C[vec[0]]);
		for (int i = 0; i < d; i ++)
			if (mask >> i & 1)
				dp[v][mask] = max(dp[v][mask], dp[v][mask - (1 << i)]);
	}
	for (int u : Ch[v])
		Add(u, dp[v][(1 << d) - 1 - (1 << rev[u])]);
	F[v] = dp[v][(1 << d) - 1];
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i ++)
	{
		scanf("%d%d%d", &A[i], &B[i], &C[i]);
		if (!C[i])
		{
			Ch[A[i]].push_back(B[i]);
			Ch[B[i]].push_back(A[i]);
		}
	}
	DFS(1, 0);
	for (int i = 1; i <= m; i ++)
		if (C[i])
		{
			if (H[A[i]] > H[B[i]])
				swap(A[i], B[i]);
			int a = A[i], b = B[i];
			int v = A[i], u = B[i];
			int cnt = 0;
			while (v != u)
			{
				cnt ++;
				if (H[v] < H[u])
					swap(v, u);
				v = P[v];
			}
			if (cnt % 2 == 1)
				continue;
			if (a == v)
			{
				int lca = v;
				v = b;
				while (H[v] > H[lca] + 1)
					v = P[v];
				V1[lca].push_back({i, b, v});
			}
			else
			{
				int lca = v;
				v = a; u = b;
				while (H[v] > H[lca] + 1)
					v = P[v];
				while (H[u] > H[lca] + 1)
					u = P[u];
				V2[lca].push_back({i, a, b, v, u});
			}
		}
	DFS2(1);
	ll SM = 0;
	for (int i = 1; i <= m; i ++)
		SM += C[i];
	SM -= dp[1][(1 << ((int)Ch[1].size())) - 1];
	return !printf("%lld\n", SM);
}

Compilation message (stderr)

training.cpp: In function 'int main()':
training.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
training.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   56 |   scanf("%d%d%d", &A[i], &B[i], &C[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• 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