oj.uz

Submission #17261

# Submission time Handle Problem Language Result Execution time Memory
17261 2015-11-11T03:55:43 Z gs14004 Beads and wires (APIO14_beads) C++14
0 / 100
 5 ms 4224 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <string>
#include <functional>
#include <vector>
#include <numeric>
#include <deque>
#include <utility>
#include <bitset>
#include <iostream>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int n;
vector<pi> graph[100005];
int dp[100005][4];

int f(int x, int m, int p){
	if(~dp[x][m]) return dp[x][m];
	if(m >= 2){
		int maxv = -1e9, sum = 0;
		for(int i=0; i<graph[x].size(); i++){
			int pos = graph[x][i].second;
			if(pos == p) continue;
			int tmp = max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
			sum += tmp;
			maxv = max(maxv, f(pos, m-2, x) + graph[x][i].first - tmp);
		}
		return dp[x][m] = sum + maxv;
	}
	else if(m == 1){
		int ret = 0;
		for(int i=0; i<graph[x].size(); i++){
			int pos = graph[x][i].second;
			if(pos == p) continue;
			ret += max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
		}
		return dp[x][m] = ret;
	}
	else{
		int sum = 0, maxv = 0;
		for(int i=0; i<graph[x].size(); i++){
			int pos = graph[x][i].second;
			if(pos == p) continue;
			int tmp1 = max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
			int tmp2 = max(f(pos, 0, x), f(pos, 2, x) + graph[x][i].first);
			sum += tmp1;
			maxv = max(maxv, tmp2 - tmp1);
		}
		int ret = sum + maxv;
		vector<int> tmp;
		sum = 0;
		for(int i=0; i<graph[x].size(); i++){
			int pos = graph[x][i].second;
			if(pos == p) continue;
			int tmp1 = max(f(pos, 1, x), f(pos, 3, x) + graph[x][i].first);
			int tmp2 = f(pos, 0, x) + graph[x][i].first;
			tmp.push_back(tmp2 - tmp1);
			sum += tmp1;
		}
		if(tmp.size() > 1){
			sort(tmp.begin(), tmp.end());
			reverse(tmp.begin(), tmp.end());
			ret = max(ret, sum + tmp[0] + tmp[1]);
		}
		return dp[x][m] = ret;
	}
}
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%d",&n);
	for(int i=0; i<n-1; i++){
		int s, e, x;
		scanf("%d %d %d",&s,&e,&x);
		graph[s].push_back(pi(x, e));
		graph[e].push_back(pi(x, s));
	}
	printf("%d",f(1, 0, 0));
}

Compilation message

beads.cpp: In function 'int f(int, int, int)':
beads.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<graph[x].size(); i++){
                ~^~~~~~~~~~~~~~~~
beads.cpp:43:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<graph[x].size(); i++){
                ~^~~~~~~~~~~~~~~~
beads.cpp:52:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<graph[x].size(); i++){
                ~^~~~~~~~~~~~~~~~
beads.cpp:63:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<graph[x].size(); i++){
                ~^~~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&s,&e,&x);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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