oj.uz

Submission #260527

# Submission time Handle Problem Language Result Execution time Memory
260527 2020-08-10T13:06:29 Z shayan_p Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 4992 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 2e5 + 10, mod = 1e9 + 7;
const ll inf = 1e18 + 10;

vector<pii> v[maxn];
ll ans[maxn], dp[maxn];

void dfs(int u, int par = -1){
    ll mx1 = -inf, mx2 = -inf, sm = 0;
    for(auto [y, c] : v[u]){
	if(y != par){
	    dfs(y, u);
	    ll x = max(ans[y], dp[y] + c);
	    sm+= x;
	    x = ans[y] - x + c;
	    if(x > mx1)
		mx2 = mx1, mx1 = x;
	    else if(x > mx2)
		mx2 = x;
	}
    }
    dp[u] = sm + mx1;
    ans[u] = max(sm, sm + mx1 + mx2);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    int n;
    cin >> n;
    for(int i = 0; i < n-1; i++){
	int a, b, c;
	cin >> a >> b >> c;
	v[a].PB({b, c});
	v[b].PB({a, c});
    }
    dfs(1);
    return cout << ans[1] << endl, 0;
}

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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