oj.uz

Submission #338148

# Submission time Handle Problem Language Result Execution time Memory
338148 2020-12-22T15:01:16 Z ogibogi2004 Beads and wires (APIO14_beads) C++14
57 / 100
 1000 ms 87372 KB 
#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];
map<int,ll>mp1[MAXN];
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);
	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

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.0 / 13.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33260 KB Output is correct
2 Correct 22 ms 33260 KB Output is correct
3 Correct 22 ms 33260 KB Output is correct
4 Correct 22 ms 33260 KB Output is correct
5 Correct 22 ms 33260 KB Output is correct
6 Correct 22 ms 33260 KB Output is correct
7 Correct 22 ms 33280 KB Output is correct
8 Correct 22 ms 33260 KB Output is correct
9 Correct 22 ms 33260 KB Output is correct
10 Correct 21 ms 33260 KB Output is correct
11 Correct 21 ms 33260 KB Output is correct
12 Correct 22 ms 33260 KB Output is correct
13 Correct 22 ms 33260 KB Output is correct
14 Correct 21 ms 33260 KB Output is correct
15 Correct 22 ms 33260 KB Output is correct
16 Correct 22 ms 33260 KB Output is correct
17 Correct 22 ms 33260 KB Output is correct
18 Correct 22 ms 33260 KB Output is correct
19 Correct 22 ms 33260 KB Output is correct
20 Correct 22 ms 33260 KB Output is correct
21 Correct 24 ms 33388 KB Output is correct
22 Correct 22 ms 33260 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33260 KB Output is correct
2 Correct 22 ms 33260 KB Output is correct
3 Correct 22 ms 33260 KB Output is correct
4 Correct 22 ms 33260 KB Output is correct
5 Correct 22 ms 33260 KB Output is correct
6 Correct 22 ms 33260 KB Output is correct
7 Correct 22 ms 33280 KB Output is correct
8 Correct 22 ms 33260 KB Output is correct
9 Correct 22 ms 33260 KB Output is correct
10 Correct 21 ms 33260 KB Output is correct
11 Correct 21 ms 33260 KB Output is correct
12 Correct 22 ms 33260 KB Output is correct
13 Correct 22 ms 33260 KB Output is correct
14 Correct 21 ms 33260 KB Output is correct
15 Correct 22 ms 33260 KB Output is correct
16 Correct 22 ms 33260 KB Output is correct
17 Correct 22 ms 33260 KB Output is correct
18 Correct 22 ms 33260 KB Output is correct
19 Correct 22 ms 33260 KB Output is correct
20 Correct 22 ms 33260 KB Output is correct
21 Correct 24 ms 33388 KB Output is correct
22 Correct 22 ms 33260 KB Output is correct
23 Correct 28 ms 34668 KB Output is correct
24 Correct 31 ms 34540 KB Output is correct
25 Correct 32 ms 34688 KB Output is correct
26 Correct 38 ms 35840 KB Output is correct
27 Correct 37 ms 35820 KB Output is correct
28 Correct 50 ms 35972 KB Output is correct
29 Correct 46 ms 35948 KB Output is correct
30 Correct 46 ms 35948 KB Output is correct
31 Correct 41 ms 36844 KB Output is correct

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 33260 KB Output is correct
2 Correct 22 ms 33260 KB Output is correct
3 Correct 22 ms 33260 KB Output is correct
4 Correct 22 ms 33260 KB Output is correct
5 Correct 22 ms 33260 KB Output is correct
6 Correct 22 ms 33260 KB Output is correct
7 Correct 22 ms 33280 KB Output is correct
8 Correct 22 ms 33260 KB Output is correct
9 Correct 22 ms 33260 KB Output is correct
10 Correct 21 ms 33260 KB Output is correct
11 Correct 21 ms 33260 KB Output is correct
12 Correct 22 ms 33260 KB Output is correct
13 Correct 22 ms 33260 KB Output is correct
14 Correct 21 ms 33260 KB Output is correct
15 Correct 22 ms 33260 KB Output is correct
16 Correct 22 ms 33260 KB Output is correct
17 Correct 22 ms 33260 KB Output is correct
18 Correct 22 ms 33260 KB Output is correct
19 Correct 22 ms 33260 KB Output is correct
20 Correct 22 ms 33260 KB Output is correct
21 Correct 24 ms 33388 KB Output is correct
22 Correct 22 ms 33260 KB Output is correct
23 Correct 28 ms 34668 KB Output is correct
24 Correct 31 ms 34540 KB Output is correct
25 Correct 32 ms 34688 KB Output is correct
26 Correct 38 ms 35840 KB Output is correct
27 Correct 37 ms 35820 KB Output is correct
28 Correct 50 ms 35972 KB Output is correct
29 Correct 46 ms 35948 KB Output is correct
30 Correct 46 ms 35948 KB Output is correct
31 Correct 41 ms 36844 KB Output is correct
32 Correct 128 ms 45824 KB Output is correct
33 Correct 124 ms 45804 KB Output is correct
34 Correct 122 ms 45804 KB Output is correct
35 Correct 528 ms 82956 KB Output is correct
36 Correct 510 ms 83180 KB Output is correct
37 Correct 515 ms 82924 KB Output is correct
38 Execution timed out 1099 ms 87372 KB Time limit exceeded
39 Halted 0 ms 0 KB -