oj.uz

Submission #667222

# Submission time Handle Problem Language Result Execution time Memory
667222 2022-11-30T20:15:57 Z manizare Beads and wires (APIO14_beads) C++14
0 / 100
 1 ms 596 KB 
#include <bits/stdc++.h>
#define all(a) a.begin(),a.end() 
#define pb push_back
#define int long long 
using namespace std ;
const int maxn = 1e4+100 , maxq =1e5 , inf = 2e18 + 100 , mod = 1e9 + 7 ;
int mark[maxn] ,dp[maxn][2] , par[maxn ];
vector <pair <int , int > > G[maxn] ;
map <pair <int ,int> , int> mp ;

void dfs(int v){
	mark[v] = 1;
	dp[v][0] = 0 ;
	vector <int> vec ;
	for(int i = 0 ; i < G[v].size() ; i++){
		int u =G[v][i].first , w = G[v][i].second ;
		if(mark[u] == 1)continue ;
		par[u] =v ;
		dfs(u);
		dp[v][0] += max(dp[u][1] , dp[u][0]);
		if(par[v] != 0)
		vec.pb(dp[u][0] + w + mp[{v , par[v]}] - max(dp[u][1] , dp[u][0]));
	}
	sort(all(vec));
	if(vec.size() > 0){
		dp[v][1] = dp[v][0] + vec.back() ;
	}
}

signed main(){	
	int n ;
	cin >> n ;
	for(int i =1 ; i < n ; i++){
		int v, u , w;
		cin >>v >> u >> w ;
		mp[{v ,u }] = mp[{u,v}] =  w;
		G[v].pb({u , w});
		G[u].pb({v , u});
	}
	int ans =0  ; 
	for(int i =1 ;i <= n ;i ++){
		memset(mark , 0 , sizeof mark);
		for(int i = 1;  i <= n ; i++){
			par[i] = 0; 
			dp[i][0] = 0 ; dp[i][1] = -inf ;
		}
		dfs(i);
	//	cout << max(dp[i][1] , dp[i][0]) << "<--\n";
		ans = max(ans , max(dp[i][1] , dp[i][0])); 
	}
	cout << ans << "\n";
}
/*
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 'void dfs(long long int)':
beads.cpp:15:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |  for(int i = 0 ; i < G[v].size() ; i++){
      |                  ~~^~~~~~~~~~~~~

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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