oj.uz

Submission #967397

# Submission time Handle Problem Language Result Execution time Memory
967397 2024-04-22T04:33:53 Z steveonalex Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 6488 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
 
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
 
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
 
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if (a > b){a = b; return true;}
        return false;
    }
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if (a < b){a = b; return true;}
        return false;
    }
template <class T>
    void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
        for(auto i: a) out << i << separator;
        out << finish;
    }
template <class T>
    void remove_dup(vector<T> &a){
        sort(ALL(a));
        a.resize(unique(ALL(a)) - a.begin());
    }

const int N = 2e5 + 69;
const ll INF = 1e18 + 69;

int n;
vector<pair<int, int>> graph[N];
ll dp[N][2];

void dfs(int u, int p){
    for(pair<int, int> v: graph[u]) if (v.first != p){
        dfs(v.first, u);
    }

    for(pair<int, int> v: graph[u]) if (v.first != p){
        dp[u][0] += max(dp[v.first][1] + v.second, dp[v.first][0]);
        ll cu = 0;
        for(pair<int, int> w: graph[u]) if (w.first != p){
            if (w.first == v.first) cu += v.second + dp[v.first][0];
            else cu += max(dp[w.first][1] + w.second, dp[w.first][0]);
        }
        maximize(dp[u][1], cu);
    }
    if (u != p) return;
    for(pair<int, int> v1: graph[u]) if (v1.first != p){
        for(pair<int, int> v2: graph[u]) if (v2.first != p){
            if (v2 >= v1) break;
            ll cu = 0;
            for(pair<int, int> v: graph[u]) if (v.first != p){
                if (v1 == v || v2 == v){
                    cu += v.second + dp[v.first][0];
                }
                else cu += max(dp[v.first][1] + v.second, dp[v.first][0]);
            }
            maximize(dp[u][0], cu);

        }
    }
}

int main(void){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;
    for(int i = 1; i<n; ++i){
        int u, v, w; cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    for(int i = 1; i<=n; ++i) sort(ALL(graph[i]));

    ll ans = 0;
    for(int i = 1; i<=n; ++i){
        for(int i = 1; i<=n; ++i) {
            dp[i][0] = 0;
            dp[i][1] = -INF;
        }
        dfs(i, i);
        maximize(ans, dp[i][0]);
    }


    cout << ans << "\n";

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 2 ms 5980 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 2 ms 5980 KB Output is correct
13 Correct 2 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 2 ms 5980 KB Output is correct
16 Correct 3 ms 5980 KB Output is correct
17 Correct 3 ms 6232 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 17 ms 6084 KB Output is correct
20 Correct 8 ms 5980 KB Output is correct
21 Correct 10 ms 6076 KB Output is correct
22 Correct 5 ms 5980 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 2 ms 5980 KB Output is correct
13 Correct 2 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 2 ms 5980 KB Output is correct
16 Correct 3 ms 5980 KB Output is correct
17 Correct 3 ms 6232 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 17 ms 6084 KB Output is correct
20 Correct 8 ms 5980 KB Output is correct
21 Correct 10 ms 6076 KB Output is correct
22 Correct 5 ms 5980 KB Output is correct
23 Correct 756 ms 6372 KB Output is correct
24 Correct 809 ms 6368 KB Output is correct
25 Correct 795 ms 6468 KB Output is correct
26 Execution timed out 1041 ms 6488 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5980 KB Output is correct
2 Correct 2 ms 5980 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 2 ms 5980 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 2 ms 5980 KB Output is correct
10 Correct 2 ms 5980 KB Output is correct
11 Correct 2 ms 5980 KB Output is correct
12 Correct 2 ms 5980 KB Output is correct
13 Correct 2 ms 5980 KB Output is correct
14 Correct 2 ms 5980 KB Output is correct
15 Correct 2 ms 5980 KB Output is correct
16 Correct 3 ms 5980 KB Output is correct
17 Correct 3 ms 6232 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 17 ms 6084 KB Output is correct
20 Correct 8 ms 5980 KB Output is correct
21 Correct 10 ms 6076 KB Output is correct
22 Correct 5 ms 5980 KB Output is correct
23 Correct 756 ms 6372 KB Output is correct
24 Correct 809 ms 6368 KB Output is correct
25 Correct 795 ms 6468 KB Output is correct
26 Execution timed out 1041 ms 6488 KB Time limit exceeded
27 Halted 0 ms 0 KB -