oj.uz

Submission #136126

# Submission time Handle Problem Language Result Execution time Memory
136126 2019-07-24T18:20:16 Z fredbr Beads and wires (APIO14_beads) C++17
57 / 100
 1000 ms 40908 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3")
 
using namespace std;
 
int const maxn = 202020;
int const inf = 0x3f3f3f3f;
 
struct Edge {
    int u, w, id;
};
 
struct FEdge {
    int a, b, w;
};
 
vector<Edge> v[2*maxn];
vector<FEdge> eg;
 
int dp[4*maxn][2];
 
inline int invalid(int x) {
    return v[x].size() == 1;
}
 
int solve(int id, int t = 0) {
    int x = eg[id].b;
 
    if (dp[id][t] >= 0) return dp[id][t];
 
    int d = 0;
 
    if (t == 0) {
        for (Edge const& e : v[x]) {
            if (e.id == (id^1)) continue;
            if (!invalid(e.u)) {
                d += max(solve(e.id, 1) + e.w, solve(e.id, 0));
            }
        }
    }
    else {
        int sum = solve(id, 0);
 
        for (Edge const& e : v[x]) {
            if (e.id == (id^1)) continue;
 
            // cout << e.u << "\n";
            if (!invalid(e.u))
                d = max(d, sum - max(solve(e.id, 1) + e.w, solve(e.id, 0))
                           + e.w + solve(e.id, 0));
            else
                d = max(d, sum + e.w);
        }
    }
 
    return dp[id][t] = d;
}
 
int main() {
    memset(dp, -1, sizeof(dp));
 
    ios::sync_with_stdio(false), cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    for (int i = 0; i < n-1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
 
        v[a].push_back({b, w, i*2});
        v[b].push_back({a, w, i*2+1});
 
        eg.push_back({a, b, w});
        eg.push_back({b, a, w});
    }
 
    for (int i = 1; i <= n; i++) {
        v[i+n].push_back({i, -inf, 2*n - 3 + i});
        eg.push_back({i+n, i, -inf});
    }
 
    int ans = 0;
    for (int i = 2*n-2; i < 3*n-2; i++) {
        ans = max(ans, solve(i));
    }
 
    cout << ans << "\n";
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16120 KB Output is correct
2 Correct 16 ms 16092 KB Output is correct
3 Correct 16 ms 16120 KB Output is correct
4 Correct 16 ms 16164 KB Output is correct
5 Correct 16 ms 16172 KB Output is correct
6 Correct 16 ms 16092 KB Output is correct
7 Correct 16 ms 16184 KB Output is correct
8 Correct 15 ms 16120 KB Output is correct
9 Correct 15 ms 16120 KB Output is correct
10 Correct 16 ms 16164 KB Output is correct
11 Correct 16 ms 16084 KB Output is correct
12 Correct 16 ms 16072 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16120 KB Output is correct
2 Correct 16 ms 16092 KB Output is correct
3 Correct 16 ms 16120 KB Output is correct
4 Correct 16 ms 16164 KB Output is correct
5 Correct 16 ms 16172 KB Output is correct
6 Correct 16 ms 16092 KB Output is correct
7 Correct 16 ms 16184 KB Output is correct
8 Correct 15 ms 16120 KB Output is correct
9 Correct 15 ms 16120 KB Output is correct
10 Correct 16 ms 16164 KB Output is correct
11 Correct 16 ms 16084 KB Output is correct
12 Correct 16 ms 16072 KB Output is correct
13 Correct 16 ms 16108 KB Output is correct
14 Correct 16 ms 16164 KB Output is correct
15 Correct 16 ms 16120 KB Output is correct
16 Correct 16 ms 16124 KB Output is correct
17 Correct 16 ms 16148 KB Output is correct
18 Correct 15 ms 16120 KB Output is correct
19 Correct 16 ms 16152 KB Output is correct
20 Correct 16 ms 16168 KB Output is correct
21 Correct 16 ms 16248 KB Output is correct
22 Correct 16 ms 16228 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16120 KB Output is correct
2 Correct 16 ms 16092 KB Output is correct
3 Correct 16 ms 16120 KB Output is correct
4 Correct 16 ms 16164 KB Output is correct
5 Correct 16 ms 16172 KB Output is correct
6 Correct 16 ms 16092 KB Output is correct
7 Correct 16 ms 16184 KB Output is correct
8 Correct 15 ms 16120 KB Output is correct
9 Correct 15 ms 16120 KB Output is correct
10 Correct 16 ms 16164 KB Output is correct
11 Correct 16 ms 16084 KB Output is correct
12 Correct 16 ms 16072 KB Output is correct
13 Correct 16 ms 16108 KB Output is correct
14 Correct 16 ms 16164 KB Output is correct
15 Correct 16 ms 16120 KB Output is correct
16 Correct 16 ms 16124 KB Output is correct
17 Correct 16 ms 16148 KB Output is correct
18 Correct 15 ms 16120 KB Output is correct
19 Correct 16 ms 16152 KB Output is correct
20 Correct 16 ms 16168 KB Output is correct
21 Correct 16 ms 16248 KB Output is correct
22 Correct 16 ms 16228 KB Output is correct
23 Correct 21 ms 16760 KB Output is correct
24 Correct 20 ms 16632 KB Output is correct
25 Correct 21 ms 16732 KB Output is correct
26 Correct 26 ms 17292 KB Output is correct
27 Correct 25 ms 17200 KB Output is correct
28 Correct 480 ms 17204 KB Output is correct
29 Correct 221 ms 17204 KB Output is correct
30 Correct 278 ms 17272 KB Output is correct
31 Correct 180 ms 17716 KB Output is correct

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 16120 KB Output is correct
2 Correct 16 ms 16092 KB Output is correct
3 Correct 16 ms 16120 KB Output is correct
4 Correct 16 ms 16164 KB Output is correct
5 Correct 16 ms 16172 KB Output is correct
6 Correct 16 ms 16092 KB Output is correct
7 Correct 16 ms 16184 KB Output is correct
8 Correct 15 ms 16120 KB Output is correct
9 Correct 15 ms 16120 KB Output is correct
10 Correct 16 ms 16164 KB Output is correct
11 Correct 16 ms 16084 KB Output is correct
12 Correct 16 ms 16072 KB Output is correct
13 Correct 16 ms 16108 KB Output is correct
14 Correct 16 ms 16164 KB Output is correct
15 Correct 16 ms 16120 KB Output is correct
16 Correct 16 ms 16124 KB Output is correct
17 Correct 16 ms 16148 KB Output is correct
18 Correct 15 ms 16120 KB Output is correct
19 Correct 16 ms 16152 KB Output is correct
20 Correct 16 ms 16168 KB Output is correct
21 Correct 16 ms 16248 KB Output is correct
22 Correct 16 ms 16228 KB Output is correct
23 Correct 21 ms 16760 KB Output is correct
24 Correct 20 ms 16632 KB Output is correct
25 Correct 21 ms 16732 KB Output is correct
26 Correct 26 ms 17292 KB Output is correct
27 Correct 25 ms 17200 KB Output is correct
28 Correct 480 ms 17204 KB Output is correct
29 Correct 221 ms 17204 KB Output is correct
30 Correct 278 ms 17272 KB Output is correct
31 Correct 180 ms 17716 KB Output is correct
32 Correct 73 ms 22376 KB Output is correct
33 Correct 72 ms 22320 KB Output is correct
34 Correct 74 ms 22312 KB Output is correct
35 Correct 352 ms 40896 KB Output is correct
36 Correct 374 ms 40828 KB Output is correct
37 Correct 348 ms 40804 KB Output is correct
38 Execution timed out 1063 ms 40908 KB Time limit exceeded
39 Halted 0 ms 0 KB -