Submission #45688

#	Time	Username	Problem	Language	Result	Execution time	Memory
45688		JohnTitor	Beads and wires (APIO14_beads)	C++11	100 / 100	487 ms	52096 KiB

beads

#include <bits/stdc++.h>
using namespace std;
#define FOR(i, j, k) for(int i=(j); i<=(k); i++)
#define FFOR(i, j, k) for(int i=(j); i<(k); i++)
#define DFOR(i, j, k) for(int i=(j); i>=(k); i--)
#define bug(x) cerr<<#x<<" = "<<(x)<<'\n'
#define pb push_back
#define mp make_pair
#define setbit(s, i) (s|=(1LL<<(i)))
#define bit(s, i) (((s)>>(i))&1LL)
#define mask(i) ((1LL<<(i)))
#define builtin_popcount __builtin_popcountll
typedef long long ll;
typedef long double ld;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define taskname "beads"
int n;
vector <pair <int, int> > g[200001];
vector <pair <int, int> > h[200001];
bool done[200001];
ll f[200001][2];
ll all[200001];
ll dtp[200001];
multiset <ll> d[200001];
void make(int u){
    if(done[u]) return;
    done[u]=1;
    f[u][0]=f[u][1]=0;
    all[u]=0;
    for(pair <int, int> v: h[u]){
        dtp[v.first]=v.second;
        make(v.first);
        d[u].insert(f[v.first][0]+dtp[v.first]-max(f[v.first][0], f[v.first][1]+dtp[v.first]));
        all[u]+=max(f[v.first][0], f[v.first][1]+v.second);
    }
    f[u][0]=all[u];
    if(d[u].empty()) f[u][1]=-mask(40);
    else f[u][1]=all[u]+*d[u].rbegin();
}
bool vs[200001];
vector <int> euler;
void dfs(int u){
    vs[u]=1;
    h[u].clear();
    euler.pb(u);
    for(pair <int, int> v: g[u]) if(!vs[v.first]){
        h[u].pb(v);
        dfs(v.first);
        euler.pb(u);
    }
}
vector <int> v;
int main(){
    #ifdef Kanikou
        if(fopen(taskname".inp", "r"))
            freopen(taskname".inp", "r", stdin);
    #endif // Kanikou
    read(n);
    {
        int a, b, c;
        FFOR(i, 1, n){
            read(a);
            read(b);
            read(c);
            g[a].pb(mp(b, c));
            g[b].pb(mp(a, c));
        }
    }
    ll ans=0;
    int root=1;
    dfs(1);
    make(1);
    ans=max(ans, f[1][0]);
    for(int u: euler){
        if(u==root) continue;
        ///make u become root
        ///push root down
        d[root].erase(d[root].find(f[u][0]+dtp[u]-max(f[u][0], f[u][1]+dtp[u])));
        all[root]-=max(f[u][0], f[u][1]+dtp[u]);
        f[root][0]=all[root];
        if(d[root].empty()) f[root][1]=-mask(40);
        else f[root][1]=all[root]+*d[root].rbegin();
        dtp[root]=dtp[u];
        ///bring u up
        d[u].insert(f[root][0]+dtp[root]-max(f[root][0], f[root][1]+dtp[root]));
        all[u]+=max(f[root][0], f[root][1]+dtp[root]);
        f[u][0]=all[u];
        if(d[u].empty()) f[u][1]=-mask(40);
        else f[u][1]=all[u]+*d[u].rbegin();
        dtp[u]=0;
        root=u;
        ans=max(ans, f[u][0]);
    }
    write(ans);
}

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