oj.uz

답안 #734305

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
734305 2023-05-02T09:20:55 Z Alihan_8 구슬과 끈 (APIO14_beads) C++17
28 / 100
 1000 ms 1364 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define pb push_back
#define ln '\n'
#define int long long

template <class _T>
bool chmin(_T &x, const _T &y){
    bool flag = false;
    if ( x > y ){
        x = y; flag |= true;
    }
    return flag;
}

template <class _T>
bool chmax(_T &x, const _T &y){
    bool flag = false;
    if ( x < y ){
        x = y; flag |= true;
    }
    return flag;
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n; cin >> n;
    vector <pair<int,int>> g[n];
    for ( int i = 1; i < n; i++ ){
        int x, y, w; cin >> x >> y >> w;
        g[--x].pb({--y, w});
        g[y].pb({x, w});
    }
    const int inf = 1e18 + 1;
    vector <array<int,2>> dp(n);
    function <void(int,int,int)> dfs = [&](int x, int par, int prev){
        int cnt = 0, l = -inf, r = -inf;
        for ( auto [to, w]: g[x] ){
            if ( to == par ) continue;
            dfs(to, x, w);
            cnt += dp[to][1];
            int v = dp[to][0] - dp[to][1] + w;
            if ( l <= v ){
                r = l; l = v;
            }
            else chmax(r, v);
        }
        dp[x][0] = cnt;
        dp[x][1] = l + cnt + prev;
        chmax(dp[x][1], dp[x][0]);
    };
    int Mx = 0;
    for ( int i = 0; i < n; i++ ){
        dfs(i, -1, 0);
        chmax(Mx, dp[i][0]);
    }
    cout << Mx;

    cout << '\n';
}
/*
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
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 2 ms 340 KB Output is correct

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 668 ms 820 KB Output is correct
24 Correct 695 ms 824 KB Output is correct
25 Correct 676 ms 820 KB Output is correct
26 Execution timed out 1070 ms 1364 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 320 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 2 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 320 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 668 ms 820 KB Output is correct
24 Correct 695 ms 824 KB Output is correct
25 Correct 676 ms 820 KB Output is correct
26 Execution timed out 1070 ms 1364 KB Time limit exceeded
27 Halted 0 ms 0 KB -