oj.uz

Submission #26098

# Submission time Handle Problem Language Result Execution time Memory
26098 2017-06-27T19:40:15 Z nibnalin Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 5120 KB 
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = int(2e5)+5, inf = int(1e9)+5;

int dp[maxn][2], dpmx[maxn], dp2[maxn];
vector<pair<int, int>> graph[maxn];

void dfs(int node, int par)
{
	pair<int, int> opt = {-inf, -inf};
	for(auto it: graph[node])
	{
		if(it.first != par)
		{
			dfs(it.first, node);
			dpmx[it.first] = max(dp[it.first][0], dp[it.first][1]+it.second);
			dp2[node] += dpmx[it.first];
			int tmp = it.second+dp[it.first][0]-dpmx[it.first];
			if(tmp > opt.first)
			{
				opt.second = opt.first;
				opt.first = tmp;
			}
			else if(tmp > opt.second)
			{
				opt.second = tmp;
			}
		}
	}

	dp[node][0] = dp2[node]+max(0, opt.first+opt.second);
	dp[node][1] = dp2[node]+opt.first;
}

int main(void)
{
	int n, u, v, c;
	scanf("%d", &n);
	for(int i = 1;i < n;i++)
	{
		scanf("%d%d%d", &u, &v, &c);
		u--, v--;
		graph[u].push_back({v, c});
		graph[v].push_back({u, c});
	}

	dfs(0, -1);
	printf("%d\n", dp[0][0]);
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &u, &v, &c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 5 ms 5120 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -