oj.uz

Submission #389168

# Submission time Handle Problem Language Result Execution time Memory
389168 2021-04-13T19:08:57 Z mosiashvililuka Beads and wires (APIO14_beads) C++14
0 / 100
 8 ms 14412 KB 
#include<bits/stdc++.h>
using namespace std;
const long long N=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,pas,dp[200009],dp2[200009];
pair <long long, long long> msh[200009];
vector <pair <long long, long long> > v[200009];
multiset <long long> s[200009];
multiset <long long>::iterator tt;
void dfsst(long long q, long long w){
	long long qw=-N;
	for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		msh[(*it).first]=make_pair(q,(*it).second);
		dfsst((*it).first,q);
		dp[q]+=max(dp[(*it).first],dp2[(*it).first]);
		if(qw<(*it).second+dp[(*it).first]-max(dp[(*it).first],dp2[(*it).first])) qw=(*it).second+dp[(*it).first]-max(dp[(*it).first],dp2[(*it).first]);
		s[q].insert((*it).second+dp[(*it).first]-max(dp[(*it).first],dp2[(*it).first]));
	}
	if(qw!=-N){
		dp2[q]=msh[q].second+dp[q]+qw;
	}else{
		dp2[q]=-N;
	}
}
void rt(long long q, long long w){
	dp[q]-=max(dp[w],dp2[w]);
	long long qw=msh[w].second+dp[w]-max(dp[w],dp2[w]);
	s[q].erase(s[q].lower_bound(qw));
	msh[q].first=w;msh[q].second=msh[w].second;
	if(s[q].size()!=0){
		tt=s[q].end();
		tt--;
		dp2[q]=msh[q].second+dp[q]+(*tt);
	}else{
		dp2[q]=-N;
	}
	s[w].insert(msh[q].second+dp[q]-max(dp[q],dp2[q]));
}
void dfs(long long q, long long w){
	pas=max(pas,dp[q]);
	for(vector <pair <long long, long long> >::iterator it=v[q].begin(); it!=v[q].end(); it++){
		if((*it).first==w) continue;
		rt(q,(*it).first);
		dfs((*it).first,q);
		rt((*it).first,q);
	}
}
int main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>a;
	for(i=1; i<a; i++){
		cin>>c>>d>>e;
		v[c].push_back(make_pair(d,e));
		v[d].push_back(make_pair(c,e));
	}
	dfsst(i,0);
	dfs(i,0);
	cout<<pas;
	return 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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