oj.uz

Submission #721944

# Submission time Handle Problem Language Result Execution time Memory
721944 2023-04-11T09:03:12 Z TB_ Beads and wires (APIO14_beads) C++14
28 / 100
 1000 ms 72768 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e12
#define fo(i, n) for(int i=0;i<(int)n;i++)
#define Fo(i, k, n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define sp(x, y) fixed<<setprecision(y)<<x
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define trr(it, x) for(auto it = x.rbegin(); it != x.rend(); it+)
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

vvpl adj(200001);
map<ll, ll> memo[200001][2];
map<ll, ll> rem[200001][2];
vpl big(200001, pl{-1, -1});
set<pl> biggest[200001];
vvl score(200001, vl(2, -1));

ll dp2(int pos, int last);

ll dp(int pos, int last){
    if(memo[pos][0].count(last)) return memo[pos][0][last];
    ll ans = 0;
    if(rem[pos][0].size() == adj[pos].size()){
        if(score[pos][0] == -1){
            score[pos][0] = 0;
            for(auto ve : rem[pos][0]){
                score[pos][0] += ve.S;
            }
        }
        // deb2(score[pos][0]-rem[pos][0][last], pos);
        // deb2(pos, last);
        // deb(score[pos][0]-rem[pos][0][last]);
        return memo[pos][0][last] = score[pos][0]-rem[pos][0][last];
    }
    for(auto v : adj[pos]){
        if(v.F == last) continue;
        ll val = max(dp(v.F, pos), dp2(v.F, pos)+v.S);
        rem[pos][0][v.F] = val;
        ans += val;
        // biggest.pb(dp(v.F, pos)+v.S-val);
    }
    memo[pos][0][last] = ans;
    // deb2(pos, last);
    // deb(ans);
    return ans;
}

ll dp2(int pos, int last){
    if(memo[pos][1].count(last)) return memo[pos][1][last];
    if(adj[pos].size() == 1) return -INF;
    if(rem[pos][1].size() == adj[pos].size()){
        return memo[pos][1][last] = score[pos][1]-rem[pos][1][last]-(last==big[pos].S?big[pos].F:0);
    }
    ll ans = 0;
    for(auto v : adj[pos]){
        if(v.F == last) continue;
        ll val = max(dp2(v.F, pos)+v.S, dp(v.F, pos));
        rem[pos][1][v.F] = val;
        ans += val;
        biggest[pos].insert({dp(v.F, pos)+v.S-val, v.F});
    }
    // deb(pos);
    if(rem[pos][1].size() == adj[pos].size()){
        // deb2(pos, last);
        if(score[pos][1] == -1){
            score[pos][1] = (*(--biggest[pos].end())).F;
            big[pos] = {(*(--biggest[pos].end())).F-(*(----biggest[pos].end())).F, (*(--biggest[pos].end())).S};
            for(auto ve : rem[pos][1]){
                score[pos][1] += ve.S;
            }
        }
        return memo[pos][1][last] = score[pos][1]-rem[pos][1][last]-(last==big[pos].S?big[pos].F:0);
    }
    if(biggest[pos].size())ans+=(*(--biggest[pos].end())).F;
    // deb2(pos, ans);
    // deb2(score[pos][1], rem[pos][1][last]);
    memo[pos][1][last] = ans;
    return ans;
}
int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit); // remove if to endof file

    int n, from, to, weight;
    cin >> n;
    fo(i, n-1){
        cin >> from >> to >> weight;
        adj[--from].pb(mp(--to, weight));
        adj[to].pb(mp(from, weight));
    }
    ll res = 0;
    fo(i, n) res = max(res, dp(i, i));
    cout << res;

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66004 KB Output is correct
2 Correct 44 ms 66076 KB Output is correct
3 Correct 46 ms 66072 KB Output is correct
4 Correct 47 ms 66012 KB Output is correct
5 Correct 37 ms 66072 KB Output is correct
6 Correct 37 ms 65980 KB Output is correct
7 Correct 38 ms 65972 KB Output is correct
8 Correct 38 ms 66004 KB Output is correct
9 Correct 38 ms 65988 KB Output is correct
10 Correct 37 ms 66040 KB Output is correct
11 Correct 37 ms 66000 KB Output is correct
12 Correct 37 ms 66072 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66004 KB Output is correct
2 Correct 44 ms 66076 KB Output is correct
3 Correct 46 ms 66072 KB Output is correct
4 Correct 47 ms 66012 KB Output is correct
5 Correct 37 ms 66072 KB Output is correct
6 Correct 37 ms 65980 KB Output is correct
7 Correct 38 ms 65972 KB Output is correct
8 Correct 38 ms 66004 KB Output is correct
9 Correct 38 ms 65988 KB Output is correct
10 Correct 37 ms 66040 KB Output is correct
11 Correct 37 ms 66000 KB Output is correct
12 Correct 37 ms 66072 KB Output is correct
13 Correct 39 ms 66132 KB Output is correct
14 Correct 38 ms 66040 KB Output is correct
15 Correct 37 ms 66132 KB Output is correct
16 Correct 38 ms 66168 KB Output is correct
17 Correct 38 ms 66208 KB Output is correct
18 Correct 40 ms 66208 KB Output is correct
19 Correct 39 ms 66140 KB Output is correct
20 Correct 38 ms 66132 KB Output is correct
21 Correct 37 ms 66156 KB Output is correct
22 Correct 37 ms 66124 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66004 KB Output is correct
2 Correct 44 ms 66076 KB Output is correct
3 Correct 46 ms 66072 KB Output is correct
4 Correct 47 ms 66012 KB Output is correct
5 Correct 37 ms 66072 KB Output is correct
6 Correct 37 ms 65980 KB Output is correct
7 Correct 38 ms 65972 KB Output is correct
8 Correct 38 ms 66004 KB Output is correct
9 Correct 38 ms 65988 KB Output is correct
10 Correct 37 ms 66040 KB Output is correct
11 Correct 37 ms 66000 KB Output is correct
12 Correct 37 ms 66072 KB Output is correct
13 Correct 39 ms 66132 KB Output is correct
14 Correct 38 ms 66040 KB Output is correct
15 Correct 37 ms 66132 KB Output is correct
16 Correct 38 ms 66168 KB Output is correct
17 Correct 38 ms 66208 KB Output is correct
18 Correct 40 ms 66208 KB Output is correct
19 Correct 39 ms 66140 KB Output is correct
20 Correct 38 ms 66132 KB Output is correct
21 Correct 37 ms 66156 KB Output is correct
22 Correct 37 ms 66124 KB Output is correct
23 Correct 64 ms 69312 KB Output is correct
24 Correct 55 ms 69324 KB Output is correct
25 Correct 49 ms 69384 KB Output is correct
26 Correct 61 ms 72768 KB Output is correct
27 Correct 62 ms 72652 KB Output is correct
28 Execution timed out 1095 ms 70344 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 66004 KB Output is correct
2 Correct 44 ms 66076 KB Output is correct
3 Correct 46 ms 66072 KB Output is correct
4 Correct 47 ms 66012 KB Output is correct
5 Correct 37 ms 66072 KB Output is correct
6 Correct 37 ms 65980 KB Output is correct
7 Correct 38 ms 65972 KB Output is correct
8 Correct 38 ms 66004 KB Output is correct
9 Correct 38 ms 65988 KB Output is correct
10 Correct 37 ms 66040 KB Output is correct
11 Correct 37 ms 66000 KB Output is correct
12 Correct 37 ms 66072 KB Output is correct
13 Correct 39 ms 66132 KB Output is correct
14 Correct 38 ms 66040 KB Output is correct
15 Correct 37 ms 66132 KB Output is correct
16 Correct 38 ms 66168 KB Output is correct
17 Correct 38 ms 66208 KB Output is correct
18 Correct 40 ms 66208 KB Output is correct
19 Correct 39 ms 66140 KB Output is correct
20 Correct 38 ms 66132 KB Output is correct
21 Correct 37 ms 66156 KB Output is correct
22 Correct 37 ms 66124 KB Output is correct
23 Correct 64 ms 69312 KB Output is correct
24 Correct 55 ms 69324 KB Output is correct
25 Correct 49 ms 69384 KB Output is correct
26 Correct 61 ms 72768 KB Output is correct
27 Correct 62 ms 72652 KB Output is correct
28 Execution timed out 1095 ms 70344 KB Time limit exceeded
29 Halted 0 ms 0 KB -