oj.uz

Submission #100181

# Submission time Handle Problem Language Result Execution time Memory
100181 2019-03-09T18:32:50 Z Plurm Beads and wires (APIO14_beads) C++11
0 / 100
 6 ms 4992 KB 
#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int> > g[200005];
long long dp[200005][2];
void dfs(int u, int p = -1){
	vector<pair<int,int> > vec;
	dp[u][1] = 0ll;
	long long smx = -1e12;
	long long mx = -1e12;
	int ccnt = 0;
	for(auto v : g[u]){
		if(v.first == p) continue;
		dfs(v.first, u);
		// Choice 1
		long long x = max(dp[v.first][0], dp[v.first][1] + v.second);
		// Choice 2
		long long y = dp[v.first][0] + v.second;
		if(y - x > mx){
			smx = mx;
			mx = y - x;
		}else if(y - x > smx){
			smx = y - x;
		}
		dp[u][0] += x;
		dp[u][1] += x;
		ccnt++;
	}
	if(ccnt >= 2){
		if(mx + smx >= 0ll) dp[u][0] += mx + smx;
	}
	if(ccnt >= 1){
		dp[u][1] += mx;
	}else{
		dp[u][1] = -1e12;
	}
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i = 1; i < n; i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		g[a].emplace_back(b,c);
		g[b].emplace_back(a,c);
	}
	dfs(1);
	printf("%lld\n",dp[1][0]);
	return 0;
}

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:43: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 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 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 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 6 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 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 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 6 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 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 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 6 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 4992 KB Output is correct
5 Correct 6 ms 4992 KB Output is correct
6 Incorrect 6 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -