oj.uz

Submission #106598

# Submission time Handle Problem Language Result Execution time Memory
106598 2019-04-19T07:25:51 Z ekrem Beads and wires (APIO14_beads) C++
0 / 100
 23 ms 23808 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define coc g[node][i].st
#define yol g[node][i].nd
#define inf 1000000007
#define N 1000005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, dp1[N], dp2[N];
vector < ii > g[N];

void dfs(int node, int par){

	if((int)g[node].size() == 1){
		dp2[node] = -inf;
		return;
	}

	int top = 0, mx = 0, mx2 = 0;
	priority_queue < int > q;
	for(int i = 0; i < g[node].size(); i++){
		if(coc == par)
			continue;
		dfs(coc, node);
		q.push(- max(dp1[coc], yol + dp2[coc]) + dp1[coc] + yol);
		// mx2 = max(mx2, - max(dp1[coc], yol + dp2[coc]) + dp1[coc] + yol);
		// if(mx2 > mx)
		// 	swap(mx, mx2);
		top += max(dp1[coc], yol + dp2[coc]);
	}
	dp2[node] = dp1[node] = top;
	// dp2[node] = max(dp2[node], top + mx);
	// dp1[node] = max(dp1[node], top + mx + mx2);
	for(int i = 0; i < g[node].size(); i++){
		if(coc == par)
			continue;
		dp2[node] = max(dp2[node], top - max(dp1[coc], yol + dp2[coc]) + dp1[coc] + yol);
	}
	if((int)q.size() >= 2){
		int of = q.top();q.pop();
		dp1[node] = max(dp1[node], top + of + q.top());
	}
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d",&n);
	for(int i = 1; i < n; i++){
		int u, v, w;
		scanf("%d %d %d",&u ,&v ,&w);
		g[u].pb(mp(v, w));
		g[v].pb(mp(u, w));
	}
	dfs(1, 0);
	printf("%d\n", dp1[1]);
	return 0;
}

Compilation message

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:27:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
beads.cpp:40:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < g[node].size(); i++){
                 ~~^~~~~~~~~~~~~~~~
beads.cpp:25:15: warning: unused variable 'mx' [-Wunused-variable]
  int top = 0, mx = 0, mx2 = 0;
               ^~
beads.cpp:25:23: warning: unused variable 'mx2' [-Wunused-variable]
  int top = 0, mx = 0, mx2 = 0;
                       ^~~
beads.cpp: In function 'int main()':
beads.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&u ,&v ,&w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Incorrect 22 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Incorrect 22 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Incorrect 22 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Incorrect 22 ms 23808 KB Output isn't correct
4 Halted 0 ms 0 KB -