oj.uz

Submission #967401

# Submission time Handle Problem Language Result Execution time Memory
967401 2024-04-22T04:50:55 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);
    }

    ll cu = 0;
    vector<ll> reduc;
    ll ma = -INF;
    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]);
        cu += max(dp[v.first][1] + v.second, dp[v.first][0]);
        maximize(ma, (v.second + dp[v.first][0]) - max(dp[v.first][1] + v.second, dp[v.first][0]));
    }
    if (ma > -INF){
        cu += ma;
        maximize(dp[u][1], cu);
    }


    if (u != p) return;
    cu = 0;
    reduc.clear();
    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 5980 KB Output is correct
2 Correct 1 ms 5980 KB Output is correct
3 Correct 2 ms 6072 KB Output is correct
4 Correct 1 ms 5976 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 5976 KB Output is correct
11 Correct 1 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 1 ms 5980 KB Output is correct
3 Correct 2 ms 6072 KB Output is correct
4 Correct 1 ms 5976 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 5976 KB Output is correct
11 Correct 1 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 5976 KB Output is correct
16 Correct 2 ms 5980 KB Output is correct
17 Correct 2 ms 5980 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 2 ms 5980 KB Output is correct
20 Correct 2 ms 6072 KB Output is correct
21 Correct 2 ms 5976 KB Output is correct
22 Correct 2 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 1 ms 5980 KB Output is correct
3 Correct 2 ms 6072 KB Output is correct
4 Correct 1 ms 5976 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 5976 KB Output is correct
11 Correct 1 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 5976 KB Output is correct
16 Correct 2 ms 5980 KB Output is correct
17 Correct 2 ms 5980 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 2 ms 5980 KB Output is correct
20 Correct 2 ms 6072 KB Output is correct
21 Correct 2 ms 5976 KB Output is correct
22 Correct 2 ms 5980 KB Output is correct
23 Correct 564 ms 6304 KB Output is correct
24 Correct 566 ms 6304 KB Output is correct
25 Correct 568 ms 6308 KB Output is correct
26 Execution timed out 1046 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 1 ms 5980 KB Output is correct
3 Correct 2 ms 6072 KB Output is correct
4 Correct 1 ms 5976 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 5976 KB Output is correct
11 Correct 1 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 5976 KB Output is correct
16 Correct 2 ms 5980 KB Output is correct
17 Correct 2 ms 5980 KB Output is correct
18 Correct 2 ms 5980 KB Output is correct
19 Correct 2 ms 5980 KB Output is correct
20 Correct 2 ms 6072 KB Output is correct
21 Correct 2 ms 5976 KB Output is correct
22 Correct 2 ms 5980 KB Output is correct
23 Correct 564 ms 6304 KB Output is correct
24 Correct 566 ms 6304 KB Output is correct
25 Correct 568 ms 6308 KB Output is correct
26 Execution timed out 1046 ms 6488 KB Time limit exceeded
27 Halted 0 ms 0 KB -