Submission #338149

#	Time	Username	Problem	Language	Result	Execution time	Memory
338149		ogibogi2004	Beads and wires (APIO14_beads)	C++14	100 / 100	802 ms	95688 KiB

beads

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
const ll INF=2e15;
int n;
vector<pair<int,ll> >g[MAXN];
set<pair<ll,int> >dp1[MAXN];
unordered_map<int,ll>mp1[MAXN];
unordered_map<int,ll>mp0[MAXN];
ll dp0v[MAXN];
int root;
ll getdp1v(int u)
{
	if(dp1[u].size()==0)return -INF;
	return dp0v[u]-(*dp1[u].begin()).first;
}
struct save1
{
	int what,where;
	ll w0,w1;
};
struct save2
{
	ll mx;
	int what,where;
	ll weight,dp0vwhat;
};
stack<save1>st1;
stack<save2>st2;
void remove(int what,int where)
{
	ll w0=mp0[where][what];
	dp0v[where]-=w0;
	ll w1=mp1[where][what];
	dp1[where].erase({w1,what});
	st1.push({what,where,w0,w1});
}
void rollback1()
{
	save1 xd=st1.top();
	st1.pop();
	dp0v[xd.where]+=xd.w0;
	dp1[xd.where].insert({xd.w1,xd.what});
}
void add(int what,int where,ll weight)
{
	ll mx=max(dp0v[what],getdp1v(what)+weight);
	dp0v[where]+=mx;
	dp1[where].insert({mx-dp0v[what]-weight,what});
	st2.push({mx,what,where,weight,dp0v[what]});
}
void rollback2()
{
	save2 xd=st2.top();st2.pop();
	dp0v[xd.where]-=xd.mx;
	dp1[xd.where].erase({xd.mx-xd.dp0vwhat-xd.weight,xd.what});
}
void dfs(int u,int p)
{
	vector<pair<pair<ll,ll>,ll> >ch;
	vector<int>ch1;
	for(auto v:g[u])
	{
		if(v.first==p)continue;
		dfs(v.first,u);
		ch.push_back({{dp0v[v.first],getdp1v(v.first)},v.second});
		ch1.push_back(v.first);
	}
	for(int i=0;i<ch.size();++i)
	{
		dp0v[u]+=max(ch[i].first.first,ch[i].first.second+ch[i].second);
		mp0[u][ch1[i]]=max(ch[i].first.first,ch[i].first.second+ch[i].second);
	}
	for(int i=0;i<ch.size();++i)
	{
		dp1[u].insert({max(ch[i].first.first,ch[i].first.second+ch[i].second)-ch[i].first.first-ch[i].second,ch1[i]});
		mp1[u][ch1[i]]=max(ch[i].first.first,ch[i].first.second+ch[i].second)-ch[i].first.first-ch[i].second;
	}
}
ll ans=0;
void dfs1(int u,int par)
{
	root=u;
	ans=max(ans,dp0v[u]);
	for(auto v:g[u])
	{
		if(v.first==par)continue;
		root=v.first;
		remove(v.first,u);
		add(u,v.first,v.second);
		dfs1(v.first,u);
		rollback1();
		rollback2();
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	srand(420);
	cin>>n;
	for(int i=1;i<n;++i)
	{
		int x,y;
		ll z;
		cin>>x>>y>>z;
		g[x].push_back({y,z});
		g[y].push_back({x,z});
	}
	dfs(1,0);
	dfs1(1,0);
	cout<<ans<<"\n";
return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:70:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i=0;i<ch.size();++i)
      |              ~^~~~~~~~~~
beads.cpp:75:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |  for(int i=0;i<ch.size();++i)
      |              ~^~~~~~~~~~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43