Submission #141412

#	Time	Username	Problem	Language	Result	Execution time	Memory
141412		khsoo01	Beads and wires (APIO14_beads)	C++11	100 / 100	455 ms	47708 KiB

beads

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18;
ll n, ans, par[200005], dt[200005][2];
ll missing[200005], sum[200005];
bool vis[200005][2];
pair<ll, ll> mx[200005][2];

vector<ll> cg[200005], cv[200005];

void update (ll cur, ll idx, ll val);
ll getsum(ll cur, ll prev);
ll solve(ll cur, ll prev, ll val);

void update (ll cur, ll idx, ll val) {
    if(mx[cur][0].second<val) {
        mx[cur][1] = mx[cur][0];
        mx[cur][0] = {idx, val};
    }
    else if(mx[cur][1].second<val) {
        mx[cur][1] = {idx, val};
    }
}

ll getsum (ll cur, ll prev) {
    if(missing[cur]) {
        if(~missing[cur]) {
            if(missing[cur] == prev) return sum[cur];
            for(int i=0;i<cg[cur].size();i++) {
                if(cg[cur][i] != missing[cur]) continue;
                sum[cur] += solve(cg[cur][i], cur, cv[cur][i]);
                update(cur, cg[cur][i], getsum(cg[cur][i],cur)-solve(cg[cur][i],cur,cv[cur][i])+cv[cur][i]);
            }
            missing[cur] = -1;
        }
        return sum[cur]-solve(prev, cur, 0);
    }
    else {
        for(int i=0;i<cg[cur].size();i++) {
            if(cg[cur][i] == prev) continue;
            sum[cur] += solve(cg[cur][i], cur, cv[cur][i]);
        }
        for(int i=0;i<cg[cur].size();i++) {
            if(cg[cur][i] == prev) continue;
            ll tmp = getsum(cg[cur][i],cur)-solve(cg[cur][i],cur,cv[cur][i])+cv[cur][i];
            update(cur, cg[cur][i], tmp);
        }
        missing[cur] = prev;
        return sum[cur];
    }
}

ll solve (ll cur, ll prev, ll val) {
    int flag = 0, piv;
    if(par[cur] != prev) {piv = prev; flag = 1;}
    else piv = cur;
    if(vis[piv][flag]) return dt[piv][flag];
    vis[piv][flag] = true;
    ll def = getsum(cur,prev), ret = def;
    ret = max(ret, def + (prev==mx[cur][0].first?mx[cur][1].second:mx[cur][0].second) + val);
    dt[piv][flag] = ret;
    return ret;
}

void precalc (ll cur, ll prev) {
    par[cur] = prev;
    for(int i=0;i<cg[cur].size();i++) {
        if(cg[cur][i] == prev) continue;
        precalc(cg[cur][i], cur);
    }
}

int main()
{
    scanf("%lld",&n);
    for(int i=1;i<n;i++) {
        ll A, B, C;
        scanf("%lld%lld%lld",&A,&B,&C);
        cg[A].push_back(B); cv[A].push_back(C);
        cg[B].push_back(A); cv[B].push_back(C);
    }
    for(int i=1;i<=n;i++) {
        for(int j=0;j<2;j++) {
            mx[i][j] = {0, -inf};
        }
    }
    precalc(1, -1);
    for(int i=1;i<=n;i++) {
        ll ret = 0;
        for(int j=0;j<cg[i].size();j++) {
            ret += solve(cg[i][j],i,cv[i][j]);
        }
        ans = max(ans, ret);
    }
    printf("%lld",ans);
}

Compilation message (stderr)

beads.cpp: In function 'll getsum(ll, ll)':
beads.cpp:30:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i=0;i<cg[cur].size();i++) {
                         ~^~~~~~~~~~~~~~~
beads.cpp:40:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<cg[cur].size();i++) {
                     ~^~~~~~~~~~~~~~~
beads.cpp:44:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<cg[cur].size();i++) {
                     ~^~~~~~~~~~~~~~~
beads.cpp: In function 'void precalc(ll, ll)':
beads.cpp:68:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<cg[cur].size();i++) {
                 ~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:91:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<cg[i].size();j++) {
                     ~^~~~~~~~~~~~~
beads.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
beads.cpp:79:14: 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