Submission #856252

#	Time	Username	Problem	Language	Result	Execution time	Memory
856252		TS_2392	Beads and wires (APIO14_beads)	C++14	100 / 100	153 ms	38340 KiB

beads

#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 (stderr)

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 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43