Submission #106928

#	Time	Username	Problem	Language	Result	Execution time	Memory
106928		nxteru	Beads and wires (APIO14_beads)	C++14	100 / 100	241 ms	26212 KiB

beads

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double D;
typedef pair<ll,ll> P;
#define M 1000000007
#define F first
#define S second
#define PB push_back
#define INF 1000000000000000000
int n;
ll da[200005],db[200005],dc[200005],dd[200005];
vector<P>g[200005];
void up(ll &x,ll y){
	if(x<y)x=y;
}
void dfs(int v,int p,ll pc){
	ll sa=0,sm=-INF,acc=-INF,acd=-INF,dm=-INF;
	for(int i=0;i<g[v].size();i++){
		int u=g[v][i].F;
		ll c=g[v][i].S;
		if(u==p)continue;
		dfs(u,v,c);
		sa+=da[u];
		up(sm,-da[u]+db[u]);
		up(dm,acc-da[u]+c+dd[u]);
		up(dm,acd-da[u]+c+dc[u]);
		up(acc,-da[u]+c+dc[u]);
		up(acd,-da[u]+c+dd[u]);
	}
	up(dc[v],sa);
	up(dd[v],sa);
	up(dd[v],sa+sm);
	up(da[v],sa+acc+pc);
	up(db[v],sa+acd+pc);
	up(dd[v],sa+dm);
	up(da[v],dc[v]);
	up(db[v],dd[v]);
}
int main(void){
	scanf("%d",&n);
	for(int i=0;i<n-1;i++){
		ll a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		g[--a].PB(P(--b,c));
		g[b].PB(P(a,c));
	}
	for(int i=0;i<n;i++)da[i]=-INF,db[i]=-INF,dc[i]=-INF,dd[i]=-INF;
	dfs(0,-1,-INF);
	printf("%lld\n",dd[0]);
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, ll)':
beads.cpp:19:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++){
              ~^~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
beads.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld",&a,&b,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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