oj.uz

답안 #139440

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
139440 2019-07-31T17:40:34 Z KLPP 구슬과 끈 (APIO14_beads) C++14
0 / 100
 54 ms 47352 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 54 ms 47224 KB Output is correct
3 Correct 46 ms 47224 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Incorrect 45 ms 47224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 54 ms 47224 KB Output is correct
3 Correct 46 ms 47224 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Incorrect 45 ms 47224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 54 ms 47224 KB Output is correct
3 Correct 46 ms 47224 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Incorrect 45 ms 47224 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 47224 KB Output is correct
2 Correct 54 ms 47224 KB Output is correct
3 Correct 46 ms 47224 KB Output is correct
4 Correct 46 ms 47352 KB Output is correct
5 Correct 45 ms 47352 KB Output is correct
6 Incorrect 45 ms 47224 KB Output isn't correct
7 Halted 0 ms 0 KB -