oj.uz

Submission #57254

# Submission time Handle Problem Language Result Execution time Memory
57254 2018-07-14T11:14:41 Z Plurm Beads and wires (APIO14_beads) C++11
0 / 100
 6 ms 4992 KB 
#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
typedef long long ll;
const int MXN = 2e5+5;
vector<pair<int,int> > g[MXN];
ll dp[MXN][2];
void dfs(int c,int p = -1){
	ll s = 0ll;
	for(int i = 0; i < g[c].size(); i++){
		pair<int,int> x = g[c][i];
		if(x.first == p) continue;
		dfs(x.first,c);
		s += max(dp[x.first][0],dp[x.first][1] + (ll)x.second);
	}
	ll m = s;
	for(int i = 0; i < g[c].size(); i++){
		if(g[c][i].first == p) continue;
		for(int j = i+1; j < g[c].size(); j++){
			if(g[c][j].first == p) continue;
			m = max(m,s 
				- max(dp[g[c][i].first][0],dp[g[c][i].first][1] + (ll)g[c][i].second)
				- max(dp[g[c][j].first][0],dp[g[c][j].first][1] + (ll)g[c][j].second) 
				+ dp[g[c][i].first][0]
				+ g[c][i].second
				+ dp[g[c][j].first][0]
				+ g[c][j].second
				);
		}
	}
	dp[c][0] = m;
	m = -1e16;
	for(int i = 0; i < g[c].size(); i++){
		if(g[c][i].first == p) continue;
		m = max(m,s + dp[g[c][i].first][0] + (ll)g[c][i].second
			- max(dp[g[c][i].first][0],dp[g[c][i].first][1] + (ll)g[c][i].second));
	}
	dp[c][1] = m;
}
int main(){
	#ifdef REDIRECT_IO
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	#endif
	int n;
	scanf("%d",&n);
	if(n > 1000) throw 0;
	int a,b,c;
	for(int i = 1; i < n; i++){
		scanf("%d%d%d",&a,&b,&c);
		g[a].eb(b,c);
		g[b].eb(a,c);
	}
	dfs(1);
	printf("%lld",dp[1][0]);
}

Compilation message

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:10:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[c].size(); i++){
                 ~~^~~~~~~~~~~~~
beads.cpp:17:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[c].size(); i++){
                 ~~^~~~~~~~~~~~~
beads.cpp:19:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = i+1; j < g[c].size(); j++){
                    ~~^~~~~~~~~~~~~
beads.cpp:33:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[c].size(); i++){
                 ~~^~~~~~~~~~~~~
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: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
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 6 ms 4992 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 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 6 ms 4992 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 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 6 ms 4992 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 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 6 ms 4992 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 -