oj.uz

Submission #856252

# Submission time Handle Problem Language Result Execution time Memory
856252 2023-10-03T01:57:28 Z TS_2392 Beads and wires (APIO14_beads) C++14
100 / 100
 153 ms 38340 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> // Common file
// #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update

using namespace std;
// using namespace __gnu_pbds;

#define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
#define SPEED         ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define EL            cout << '\n'
#define dbg(x)        cout << #x << " = " << (x) << ' '
#define dbgp(x)       cout << #x << " = (" << (x.fi) << ", " << (x.se) << ") "
#define dbga(x, l, r) {cout << #x << '[' << l << ", " << r << "] = { "; for(int i = l; i <= (int)r; ++i) cout << x[i] << ' '; cout << "} ";}

#define epl           emplace
#define pb            push_back
#define eb            emplace_back
#define fi            first
#define se            second
#define mp            make_pair

#define sqr(x)        ((x) * (x))
#define all(x)        (x).begin(), (x).end()
#define rall(x)       (x).rbegin(), (x).rend()
#define lwb           lower_bound
#define upb           upper_bound
#define ctz           __builtin_ctzll // or __builtin_ctz
#define pct           __builtin_popcountll // or __builtin_popcount

typedef long long            ll;
typedef long double          ldb;
typedef unsigned int         uint;
typedef unsigned long long   ull;
typedef pair<ll, ll>         pll;
typedef pair<ll, int>        pli;
typedef pair<int, ll>        pil;
typedef pair<int, int>       pii;
typedef pair<ldb, ldb>       pld;
typedef pair<double, double> pdd;

template<class T1, class T2> bool minimize(T1 &a, T2 b){return a > b ? a = b, true : false;}
template<class T1, class T2> bool maximize(T1 &a, T2 b){return a < b ? a = b, true : false;}

// int d4x[4] = {1, 0, -1, 0}, d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
// int d4y[4] = {0, 1, 0, -1}, d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
const int N = 2e5 + 3;
const ll oo = 1e18;
int n;
ll dp[N][2], f[N][2], res = -oo;
vector<pil> adj[N];
void dfs1(int u, int par){
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i].fi;
        if(v == par) continue;
        dfs1(v, u);
        ll w = adj[u][i].se;
        dp[u][0] += max(dp[v][0], dp[v][1] + w);
    }
    for(int i = 0; i < adj[u].size(); ++i){
        int v = adj[u][i].fi;
        if(v == par) continue;
        ll w = adj[u][i].se;
        maximize(dp[u][1], dp[u][0] - max(dp[v][0], dp[v][1] + w) + dp[v][0] + w);
    }
    if(u == 1) res = dp[u][0];
}
void dfs2(int u, int par, ll w_u_par){
    pii best = {-1, -1};
    int sz = adj[u].size(), num_child = 0;
    vector<ll> contrib(sz), a(sz);

    if(u != 1) maximize(res, dp[u][0] + max(f[u][0], f[u][1] + w_u_par));
    ll contrib_par = max(f[u][1] + w_u_par, f[u][0]);

    for(int i = 0; i < sz; ++i){
        int v = adj[u][i].fi;
        if(v == par) continue;
        ll w = adj[u][i].se;
        ++num_child;

        contrib[i] = max(dp[v][0], dp[v][1] + w);
        a[i] = -contrib[i] + w + dp[v][0];

        f[v][0] = contrib_par + dp[u][0] - contrib[i];
        if(u != 1) f[v][1] = f[u][0] + w_u_par + dp[u][0] - contrib[i];
        //neu chon cha cua u de noi tiep, neu u = 1 thi ko co cha nen ko the lam theo cach nay

        if(best.fi == -1 || a[best.fi] < a[i]){
            best.se = best.fi;
            best.fi = i;
        }
        else if(best.se == -1 || a[best.se] < a[i]){
            best.se = i;
        }
    }
    //neu chon mot con khac v cua u de noi tiep
    if(num_child > 1) for(int i = 0; i < sz; ++i){
        int v = adj[u][i].fi;
        ll add_val = (i == best.fi ? a[best.se] : a[best.fi]);
        maximize(f[v][1], contrib_par + dp[u][0] - contrib[i] + add_val);
    }

    contrib.clear(); a.clear();
    for(int i = 0; i < sz; ++i){
        int v = adj[u][i].fi;
        if(v == par) continue;
        dfs2(v, u, adj[u][i].se);
    }
}
void TS_2392(){
    cin >> n;
    for(int i = 1; i < n; ++i){
        int u, v; ll w;
        cin >> u >> v >> w;
        adj[u].eb(v, w); adj[v].eb(u, w);
    }
    for(int i = 1; i <= n; ++i){
        f[i][1] = dp[i][1] = -oo;
    }
    dfs1(1, 0); dfs2(1, 0, -oo);
    cout << res;
}
int main(){
    SPEED; fileIO("text1");
    int num_test = 1; //cin >> num_test;
    for(int itest = 1; itest <= num_test; ++itest){
        TS_2392();
    }
    return 0;
}

Compilation message

beads.cpp: In function 'void dfs1(int, int)':
beads.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int i = 0; i < adj[u].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~
beads.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < adj[u].size(); ++i){
      |                    ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:8:58: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:127:12: note: in expansion of macro 'fileIO'
  127 |     SPEED; fileIO("text1");
      |            ^~~~~~
beads.cpp:8:91: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | #define fileIO(name)  if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);}
      |                                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
beads.cpp:127:12: note: in expansion of macro 'fileIO'
  127 |     SPEED; fileIO("text1");
      |            ^~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8816 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8848 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 1 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 2 ms 9088 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 1 ms 8804 KB Output is correct
20 Correct 2 ms 8848 KB Output is correct
21 Correct 2 ms 9048 KB Output is correct
22 Correct 2 ms 8796 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8816 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8848 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 1 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 2 ms 9088 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 1 ms 8804 KB Output is correct
20 Correct 2 ms 8848 KB Output is correct
21 Correct 2 ms 9048 KB Output is correct
22 Correct 2 ms 8796 KB Output is correct
23 Correct 4 ms 9052 KB Output is correct
24 Correct 3 ms 9120 KB Output is correct
25 Correct 5 ms 9304 KB Output is correct
26 Correct 6 ms 9308 KB Output is correct
27 Correct 6 ms 9288 KB Output is correct
28 Correct 4 ms 9432 KB Output is correct
29 Correct 4 ms 9560 KB Output is correct
30 Correct 5 ms 9368 KB Output is correct
31 Correct 6 ms 10588 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8792 KB Output is correct
2 Correct 1 ms 8796 KB Output is correct
3 Correct 1 ms 8796 KB Output is correct
4 Correct 1 ms 8816 KB Output is correct
5 Correct 1 ms 8792 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 1 ms 8796 KB Output is correct
8 Correct 1 ms 8848 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 1 ms 8792 KB Output is correct
11 Correct 2 ms 8796 KB Output is correct
12 Correct 1 ms 8796 KB Output is correct
13 Correct 2 ms 9088 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 2 ms 8796 KB Output is correct
16 Correct 2 ms 8796 KB Output is correct
17 Correct 2 ms 8796 KB Output is correct
18 Correct 2 ms 8796 KB Output is correct
19 Correct 1 ms 8804 KB Output is correct
20 Correct 2 ms 8848 KB Output is correct
21 Correct 2 ms 9048 KB Output is correct
22 Correct 2 ms 8796 KB Output is correct
23 Correct 4 ms 9052 KB Output is correct
24 Correct 3 ms 9120 KB Output is correct
25 Correct 5 ms 9304 KB Output is correct
26 Correct 6 ms 9308 KB Output is correct
27 Correct 6 ms 9288 KB Output is correct
28 Correct 4 ms 9432 KB Output is correct
29 Correct 4 ms 9560 KB Output is correct
30 Correct 5 ms 9368 KB Output is correct
31 Correct 6 ms 10588 KB Output is correct
32 Correct 21 ms 14172 KB Output is correct
33 Correct 21 ms 14172 KB Output is correct
34 Correct 22 ms 14204 KB Output is correct
35 Correct 153 ms 25176 KB Output is correct
36 Correct 126 ms 25168 KB Output is correct
37 Correct 132 ms 25076 KB Output is correct
38 Correct 80 ms 27572 KB Output is correct
39 Correct 97 ms 27668 KB Output is correct
40 Correct 113 ms 27048 KB Output is correct
41 Correct 135 ms 38340 KB Output is correct