Submission #721354

#	Time	Username	Problem	Language	Result	Execution time	Memory
721354		n0sk1ll	Beads and wires (APIO14_beads)	C++14	0 / 100	3 ms	4948 KiB

beads

#include <bits/stdc++.h>

#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cerr.tie(0)
#define mp make_pair
#define xx first
#define yy second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define all(x) x.begin(),x.end()
#define ff(i,a,b) for (li i = a; i < b; i++)
#define fff(i,a,b) for (int i = a; i <= b; i++)
#define bff(i,a,b) for (int i = b-1; i >= a; i--)
#define bfff(i,a,b) for (int i = b; i >= a; i--)

using namespace std;
long double typedef ld;
unsigned int typedef ui;
long long int typedef li;
pair<int,int> typedef pii;
pair<li,li> typedef pli;
pair<ld,ld> typedef pld;
vector<vector<int>> typedef graph;
unsigned long long int typedef ull;
//const int mod = 998244353;
const int mod = 1000000007;







//Note to self: Check for overflow

vector<vector<pli>> g(200005);
li dp[200005]; //optimalan ans za subtree
li dpdole[200005]; //uzimam iskljucivo dole
li dpgore[200005]; //uzimam iskljucivo gore

void dfs(li p, li q, li qw)
{
    vector<li> profit; //koliko profitiram ako uzmem dpdole[child] i ostavim sebi grane za naknadno uparivanje
    for (auto it : g[p]) if (it.xx!=q)
    {
        dfs(it.xx,p,it.yy);
        dpdole[p]+=dp[it.xx];
        profit.pb(dpdole[it.xx]-dp[it.xx]+it.yy);
    }
    sort(all(profit),greater<li>());

    if (profit.empty()) dpgore[p]=-mod;
    if ((li)profit.size()>=1) dpgore[p]=dpdole[p]+qw+profit[0];
    if ((li)profit.size()>=2) dpdole[p]=max(dpdole[p],dpdole[p]+profit[0]+profit[1]);

    dp[p]=max(dpdole[p],dpgore[p]);
}

int main()
{
    li n; cin>>n;
    ff(i,1,n)
    {
        li u,v,w; cin>>u>>v>>w;
        g[u].pb({v,w}),g[v].pb({u,w});
    }
    dfs(1,0,-mod);

    cout<<dp[1]<<"\n";
}

//Note to self: Check for overflow

/*

5
1 2 10
1 3 40
1 4 15
1 5 20

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

*/

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