oj.uz

Submission #22070

# Submission time Handle Problem Language Result Execution time Memory
22070 2017-04-29T07:07:03 Z amsen Beads and wires (APIO14_beads) C++11
13 / 100
 11 ms 5120 KB 
//in the name of allah
#include<vector>
#include<iostream>
#include<map>
#include<bitset>
#include<algorithm>
#include<set>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 2e5+1 , inf = 1e9;
typedef pair<int , int> ii;
int dpr[maxn] , dpe[maxn] , dp[maxn] , dpt[maxn] , n;
vector<ii> g[maxn];
void dfs(int v , int par){
	dpe[v] = -1e9;
	dpt[v] = -1e9;
	int sum=0;
	set<ii> st;
	for(auto U : g[v]){
		int u = U.first , w = U.second;
		if(u == par)
			continue;
		dfs(u , v);
		int cur = max(dpe[u] + w , dp[u]);
		sum += cur;
		st.insert(ii(w+dpr[u]-cur , u));
	}
	dpr[v] = sum;
	dp[v] = dpr[v];
	for(auto U : g[v]){
		int u = U.first , w = U.second;
		if(u == par)
			continue;
		int cur = max(dpe[u] + w , dp[u]);
		dpt[v] = max(dpt[v] , sum - cur + w + dp[u]);
		dpe[v] = max(dpe[v] , sum - cur + w + dpr[u]);
		st.erase(ii(w+dpr[u]-cur , u));
		if((int)st.size())
			dp[v] = max(dp[v] , dp[u] + w + sum - cur + st.rbegin()->first);
		dp[v] = max(dp[v] , dpt[u] + w + sum - cur);
		st.insert(ii(w+dpr[u]-cur , u));
	}
}

int main(){
	scanf("%d" , &n);
	for(int i=0 ; i<n-1 ; i++){
		int v , u , w;
		scanf("%d%d%d" , &v , &u , &w);
		v --;
		u --;
		g[v].push_back(ii(u , w));
		g[u].push_back(ii(v , w));
	}
	dfs(0 , -1);
	printf("%d\n" , dp[0]);
}
/*
10
4 10 2 1 2 21 1 3 13 6 7 1 7 9 5 2 4 3 2 5 8 1 6 55 6 8 34
*/

Compilation message

beads.cpp: In function 'int main()':
beads.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d" , &n);
  ~~~~~^~~~~~~~~~~
beads.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d" , &v , &u , &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 11 ms 5120 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 11 ms 5120 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Incorrect 6 ms 4992 KB Output isn't correct
14 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 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 11 ms 5120 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Incorrect 6 ms 4992 KB Output isn't correct
14 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 5120 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 5 ms 4992 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 6 ms 5120 KB Output is correct
11 Correct 11 ms 5120 KB Output is correct
12 Correct 6 ms 4992 KB Output is correct
13 Incorrect 6 ms 4992 KB Output isn't correct
14 Halted 0 ms 0 KB -