Submission #139440

#	Time	Username	Problem	Language	Result	Execution time	Memory
139440		KLPP	Beads and wires (APIO14_beads)	C++14	0 / 100	54 ms	47352 KiB

beads

#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define INF 10000000000000000
vector<pii> nei[1000000];
bool visited[1000000];
vector<pii> child[1000000];
void DFS(int node){
  visited[node]=true;
  trav(a,nei[node]){
    if(!visited[a.first]){
      DFS(a.first);
      child[node].push_back(a);
    }
  }
}
lld DP[10000000][2];
lld calc(int node, int type){
  if(DP[node][type]!=-1)return DP[node][type];
  DP[node][type]=0;
  if(type==1){
    lld sum=0;
    lld M=-INF;
    trav(a,child[node]){
      sum+=max(calc(a.first,0),calc(a.first,1)+a.second);
      M=max(M,calc(a.first,0)+a.second-max(calc(a.first,0),calc(a.first,1)+a.second));
    }
    DP[node][type]=sum+M;
    return DP[node][type];
  }
  vector<lld> v;
  lld sum=0;
  trav(a,child[node]){
    sum+=max(calc(a.first,0),calc(a.first,1)+a.second);
    v.push_back(calc(a.first,0)+a.second-max(calc(a.first,0),calc(a.first,1)+a.second));
  }
  sort(v.begin(),v.end());
  reverse(v.begin(),v.end());
  DP[node][type]=sum;
  if(v.size()>1){
    DP[node][type]=max(DP[node][type],sum+v[0]+v[1]);
  }
  return DP[node][type];
}
int main(){
  int n;
  cin>>n;
  rep(i,0,n)visited[i]=false;
  rep(i,0,n-1){
    lld x,y,z;
    cin>>x>>y>>z;
    x--;y--;
    nei[x].push_back(pii(y,z));
    nei[y].push_back(pii(x,z));
  }
  DFS(0);
  rep(i,0,n){
    DP[i][0]=-1;
    DP[i][1]=-1;
  }
  cout<<calc(0,0)<<endl;
  return 0;
}

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