oj.uz

Submission #122305

# Submission time Handle Problem Language Result Execution time Memory
122305 2019-06-28T04:32:45 Z 김세빈(#2988) Beads and wires (APIO14_beads) C++14
0 / 100
 6 ms 5120 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> T[202020], K;
int V[404040], C[202020], S[404040];
int A[404040], B[404040];
int D[202020], M1[202020], M2[202020];
int n, ans;

int dfs(int p, int r)
{
	int k, ret = 1;
	
	for(int &t: T[p]){
		if(V[t] != r){
			k = dfs(V[t], p);
			S[t] = k; S[t ^ 1] = n - k;
			ret += k;
		}
	}
	
	return ret;
}

int main()
{
	int i, u, v;
	
	scanf("%d", &n);
	
	for(i=0; i<n-1; i++){
		scanf("%d%d%d", V + (i << 1), V + (i << 1 | 1), C + i);
		T[V[i << 1]].push_back(i << 1 | 1);
		T[V[i << 1 | 1]].push_back(i << 1);
	}
	
	dfs(1, 0);
	
	for(i=0; i<n+n-2; i++){
		K.push_back(i);
	}
	
	sort(K.begin(), K.end(), [&](int &a, int &b){
		return S[a] < S[b];
	});
	
	for(i=1; i<=n; i++){
		M1[i] = M2[i] = -2e9;
	}
	
	for(int &t: K){
		u = V[t], v = V[t ^ 1];
		A[t] = D[u] - max(A[t ^ 1], B[t ^ 1]);
		B[t] = A[t] + C[t >> 1] + (min(0, A[t ^ 1] - B[t ^ 1]) + C[t >> 1] != M1[u]? M1[u] : M2[u]);
		
		D[v] += max(A[t], B[t]);
		if(M1[v] < min(0, A[t] - B[t]) + C[t >> 1]) M2[v] = M1[v], M1[v] = min(0, A[t] - B[t]) + C[t >> 1];
		else if(M2[v] < min(0, A[t] - B[t]) + C[t >> 1]) M2[v] = min(0, A[t] - B[t]) + C[t >> 1];
	}
	
	for(i=1; i<=n; i++){
		ans = max(ans, D[i]);
	}
	
	printf("%d\n", ans);
	
	return 0;
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
beads.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", V + (i << 1), V + (i << 1 | 1), C + i);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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