oj.uz

Submission #15853

# Submission time Handle Problem Language Result Execution time Memory
15853 2015-07-31T12:11:44 Z myungwoo Beads and wires (APIO14_beads) C++14
13 / 100
 10 ms 9728 KB 
#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()

int N;
int D[MAXN], E[MAXN], F[MAXN], G[MAXN];
int up[MAXN], V[MAXN];
vector <int> con[MAXN], conv[MAXN];

void dfs(int n, int from)
{
	vector <int> arr;
	for (int i=sz(con[n]);i--;){
		int t = con[n][i], v = conv[n][i];
		if (t == from) continue;
		up[t] = v; dfs(t, n);
		arr.pb(t);
	}
	D[n] = E[n] = F[n] = G[n] = 0;
	int def = 0;
	for (int t: arr){
		V[t] = max(max(D[t], E[t]), F[t]);
		D[n] += max(V[t], G[t]);
		def += V[t];
	}
	int mx1 = -2e9, mx2 = -2e9;
	for (int t: arr){
		if (mx1 > -2e9){
			E[n] = max(E[n], def + mx1 + E[t] - V[t] + up[t]);
			E[n] = max(E[n], def + max(mx1, mx2) + D[t] - V[t] + up[t]);
		}
		mx1 = max(mx1, -V[t]+D[t]+up[t]);
		mx2 = max(mx2, -V[t]+E[t]+up[t]);
	}
	for (int t: arr){
		F[n] = max(F[n], def - V[t] + D[t] + up[t] + up[n]);
		G[n] = max(G[n], def - V[t] + E[t] + up[t] + up[n]);
	}
}

int main()
{
	scanf("%d", &N);
	for (int i=1;i<N;i++){
		int a, b, c;
		scanf("%d%d%d", &a, &b, &c);
		con[a].pb(b); conv[a].pb(c);
		con[b].pb(a); conv[b].pb(c);
	}
	dfs(1, 0);
	printf("%d\n", max(D[1], E[1]));
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
beads.cpp:50: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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9728 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 9 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 9 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9728 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 9 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 9 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct
13 Incorrect 10 ms 9728 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9728 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 9 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 9 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct
13 Incorrect 10 ms 9728 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 9728 KB Output is correct
2 Correct 10 ms 9728 KB Output is correct
3 Correct 10 ms 9728 KB Output is correct
4 Correct 9 ms 9728 KB Output is correct
5 Correct 9 ms 9728 KB Output is correct
6 Correct 9 ms 9728 KB Output is correct
7 Correct 9 ms 9728 KB Output is correct
8 Correct 9 ms 9728 KB Output is correct
9 Correct 9 ms 9728 KB Output is correct
10 Correct 9 ms 9728 KB Output is correct
11 Correct 9 ms 9728 KB Output is correct
12 Correct 9 ms 9728 KB Output is correct
13 Incorrect 10 ms 9728 KB Output isn't correct
14 Halted 0 ms 0 KB -