oj.uz

Submission #721354

# Submission time Handle Problem Language Result Execution time Memory
721354 2023-04-10T18:19:24 Z n0sk1ll Beads and wires (APIO14_beads) C++14
0 / 100
 3 ms 4948 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 2 ms 4948 KB Output is correct
6 Incorrect 3 ms 4948 KB Output isn't correct
7 Halted 0 ms 0 KB -