oj.uz

Submission #297142

# Submission time Handle Problem Language Result Execution time Memory
297142 2020-09-11T09:52:15 Z Kastanda Training (IOI07_training) C++11
100 / 100
 87 ms 4736 KB 
// 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

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.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
7.0 / 7.0

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

Subtask #5
9.0 / 9.0

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

Subtask #6
9.0 / 9.0

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

Subtask #7
9.0 / 9.0

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

Subtask #8
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1152 KB Output is correct
2 Correct 5 ms 1024 KB Output is correct
3 Correct 35 ms 1664 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2432 KB Output is correct
2 Correct 54 ms 1656 KB Output is correct
3 Correct 9 ms 1664 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1120 KB Output is correct
2 Correct 4 ms 1792 KB Output is correct
3 Correct 87 ms 4728 KB Output is correct
4 Correct 8 ms 1920 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2424 KB Output is correct
2 Correct 45 ms 4728 KB Output is correct
3 Correct 26 ms 1944 KB Output is correct
4 Correct 84 ms 1784 KB Output is correct