oj.uz

Submission #967399

# Submission time Handle Problem Language Result Execution time Memory
967399 2024-04-22T04:42:17 Z steveonalex Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 6496 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;
    ll cu = 0;
    vector<ll> reduc;
    for(pair<int, int> v: graph[u]) if (v.first != p){
        cu += max(dp[v.first][1] + v.second, dp[v.first][0]);
        reduc.push_back((v.second + dp[v.first][0]) - max(dp[v.first][1] + v.second, dp[v.first][0]));
    }
    if (reduc.size() < 2) return;
    nth_element(reduc.begin(), reduc.begin() + 1, reduc.end(), greater<ll>());
    for(int i = 0; i<=1; ++i) cu += reduc[i];
    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 5976 KB Output is correct
2 Correct 2 ms 5976 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 5976 KB Output is correct
9 Correct 1 ms 5980 KB Output is correct
10 Correct 2 ms 5976 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 5976 KB Output is correct
2 Correct 2 ms 5976 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 5976 KB Output is correct
9 Correct 1 ms 5980 KB Output is correct
10 Correct 2 ms 5976 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 2 ms 5980 KB Output is correct
17 Correct 3 ms 5980 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 12 ms 6076 KB Output is correct
20 Correct 7 ms 5980 KB Output is correct
21 Correct 8 ms 5980 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 2 ms 5976 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 5976 KB Output is correct
9 Correct 1 ms 5980 KB Output is correct
10 Correct 2 ms 5976 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 2 ms 5980 KB Output is correct
17 Correct 3 ms 5980 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 12 ms 6076 KB Output is correct
20 Correct 7 ms 5980 KB Output is correct
21 Correct 8 ms 5980 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 788 ms 6312 KB Output is correct
24 Correct 846 ms 6496 KB Output is correct
25 Correct 795 ms 6308 KB Output is correct
26 Execution timed out 1066 ms 6492 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 5976 KB Output is correct
2 Correct 2 ms 5976 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 5976 KB Output is correct
9 Correct 1 ms 5980 KB Output is correct
10 Correct 2 ms 5976 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 2 ms 5980 KB Output is correct
17 Correct 3 ms 5980 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 12 ms 6076 KB Output is correct
20 Correct 7 ms 5980 KB Output is correct
21 Correct 8 ms 5980 KB Output is correct
22 Correct 4 ms 5980 KB Output is correct
23 Correct 788 ms 6312 KB Output is correct
24 Correct 846 ms 6496 KB Output is correct
25 Correct 795 ms 6308 KB Output is correct
26 Execution timed out 1066 ms 6492 KB Time limit exceeded
27 Halted 0 ms 0 KB -