oj.uz

답안 #462258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
462258 2021-08-10T09:06:20 Z azberjibiou 구슬과 끈 (APIO14_beads) C++17
0 / 100
 6 ms 9720 KB 
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=200010;
const int mxM=7300000;
const int mxK=100001;
const int MOD=1000000007;
const ll INF=9223372036854775807;
int N;
vector <pii> v[mxN];
vector <pii> adj[mxN];
ll par[mxN];
ll dp1[mxN], dp2[mxN];
typedef struct cmp1{
    bool operator()(ll a, ll b)
    {
        return a>b;
    }
}cmp1;
void dfs(int now, int pre)
{
    priority_queue <ll> pq;
    ll sum1=0;
    for(pii nxt : v[now])   if(nxt.fir!=pre)
    {
        par[nxt.fir]=nxt.sec;
        dfs(nxt.fir, now);
        sum1+=dp1[nxt.fir];
        pq.push(dp2[nxt.fir]+nxt.sec-dp1[nxt.fir]);
    }
    ll tmp1, tmp2;
    if(pq.empty())
    {
        dp2[now]=dp1[now]=0;
        return;
    }
    if(pq.size()==1)
    {
        dp2[now]=sum1;
        dp1[now]=max(dp2[now], sum1+par[now]+pq.top());
        return;
    }
    //assert(pq.size()==2);
    tmp1=pq.top();
    pq.pop();
    tmp2=pq.top();
    pq.pop();
    //printf("tmp1=%lld, tmp2=%lld\n", tmp1, tmp2);
    dp2[now]=sum1+tmp1+tmp2;
    dp1[now]=max(dp2[now], sum1+par[now]+tmp1);
}
int main()
{
    gibon
    cin >> N;
    if(N<=2)
    {
        cout << 0;
        return 0;
    }
    for(int i=1;i<N;i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    dfs(3, -1);
    cout << dp2[3];
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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