oj.uz

답안 #713087

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
713087 2023-03-21T03:37:11 Z bin9638 구슬과 끈 (APIO14_beads) C++17
0 / 100
 5 ms 8148 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define N 200010
#define ii pair<int,int>
#define fs first
#define sc second
#define ld double
#define int ll

int dp[N][2],n;
vector<ii>g[N];

void selfmax(int&u,int v)
{
    u=max(u,v);
}

void DFS(int u,int p)
{
    dp[u][0]=0;
    for(auto v:g[u])
        if(v.sc!=p)
            DFS(v.sc,u);
    //dp[u][0]
    int f[4];
    f[0]=f[1]=f[2]=f[3]=-1e12;
    for(auto v:g[u])
        if(v.sc!=p)
        {
            dp[u][0]+=max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            f[3]=dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            sort(f,f+4,greater<int>());
            //cout<<u<<" "<<v.sc<<" "<<dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)<<endl;
        }
    int dm=dp[u][0];
    selfmax(dp[u][0],dp[u][0]+f[0]+f[1]);
    //dp[v.sc][1]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)
    //dp[u][1]
    for(auto v:g[u])
        if(v.sc!=p)
        {
            int sum=dm-max(dp[v.sc][0],dp[v.sc][1]+v.fs);
            if(dp[v.sc][0]+v.fs-max(dp[v.sc][0],dp[v.sc][1]+v.fs)!=f[0])
                selfmax(dp[u][1],dp[v.sc][0]+v.fs+sum+max(0ll,f[0]+f[1]));
                    else  selfmax(dp[u][1],dp[v.sc][0]+v.fs+sum+max(0ll,f[2]+f[1]));
        }
    //cout<<u<<" "<<dp[u][0]<<" "<<dp[u][1]<<endl;
}

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    memset(dp,-0x3f3f,sizeof(dp));
    cin>>n;
    int sum=0;
    for(int i=1;i<n;i++)
    {
        int u,v,L;
        cin>>u>>v>>L;
        g[u].pb({L,v});
        g[v].pb({L,u});
        sum+=L;
    }
    //cout<<sum<<endl;
    DFS(1,0);
    cout<<dp[1][0];
    return 0;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8020 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8020 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8020 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 8020 KB Output is correct
2 Correct 5 ms 8148 KB Output is correct
3 Incorrect 4 ms 8148 KB Output isn't correct
4 Halted 0 ms 0 KB -