oj.uz

Submission #169981

# Submission time Handle Problem Language Result Execution time Memory
169981 2019-12-23T13:47:00 Z ZwariowanyMarcin Beads and wires (APIO14_beads) C++14
0 / 100
 7 ms 4984 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define ss(x) (int) x.size()
#define pb push_back
#define ll long long
#define cat(x) cerr << #x << " = " << x << endl
#define FOR(i, n) for(int i = 0; i < n; ++i)

using namespace std;	

const int nax = 2e5 + 111;
const ll inf = 1e18;

int n;
int a, b, c;
vector <pair<int,int>> v[nax];

ll dp[nax][3];

void dfs(int u, int p, int cost) {
	dp[u][0] = 0;
	dp[u][1] = -inf;
	ll sum = 0;
	vector <ll> opt;
	for(auto it : v[u]) 
		if(it.fi != p) {
			dfs(it.fi, u, it.se);
			sum += dp[it.fi][2];
			opt.pb(it.se + dp[it.fi][0] - dp[it.fi][2]);
		}
	sort(opt.begin(), opt.end());
	reverse(opt.begin(), opt.end());
	dp[u][0] = max(dp[u][0], sum);
	if(ss(opt) > 1)
		dp[u][0] = max(dp[u][0], sum + opt[0] + opt[1]);
	if(ss(opt) > 0 && p != 0)
		dp[u][1] = max(dp[u][1], sum + opt[0] + cost);
	dp[u][2] = max(dp[u][0], dp[u][1]);
}
		
		
			
int main() {
	scanf("%d", &n);
	for(int i = 1; i < n; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		v[a].pb(mp(b, c));
		v[b].pb(mp(a, c));
	}
	dfs(1, 0, 0);
	printf("%lld", dp[1][0]);
	
	
	return 0;
}

Compilation message

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

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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