oj.uz

Submission #890054

# Submission time Handle Problem Language Result Execution time Memory
890054 2023-12-20T12:38:16 Z Kutan Beads and wires (APIO14_beads) C++14
100 / 100
 125 ms 22308 KB 
// Cao Quang Hung
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long , long long>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define dem(x) __builtin_popcount(x)
#define Mask(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ln '\n'
#define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
///mt19937 rnd(time(0));

const int INF = 1e9 , mod = 1e9 + 7;

template <class T1, class T2>
inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }

template <class T1 , class T2>
inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}

template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }

template <class T>
inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }

template <class T>
inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }

#define PROB "a"
void file(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
}
void sinh_(){
//    srand(time(0));
//    freopen(PROB".inp" , "w" , stdout);
//    int n;
}

typedef long long ll;
typedef double db;
const int N = 2e5 + 5;

vpii adj[N];
int dp[N][2], n;
int f[N][2];
int res = 0;

inline void readip(){
    cin >> n;
    REP(i, 2, n) {
        int u, v, c; cin >> u >> v >> c;
        adj[u].eb(v, c);
        adj[v].eb(u, c);
    }
}

inline void dfs_tree(int u, int p = -1) {
    dp[u][0] = 0;
    f[u][0] = f[u][1] = -1e9;
    for (const auto &[v, w] : adj[u]) {
        if (v == p) continue;
        dfs_tree(v, u);

        dp[u][0] += max(w + dp[v][1], dp[v][0]);
        int val = dp[v][0] + w - max(w + dp[v][1], dp[v][0]);
        if (val > f[u][0]) f[u][1] = f[u][0], f[u][0] = val;
        else maximize(f[u][1], val);
   
    }   
    dp[u][1] = dp[u][0] + f[u][0];
}

void reroot(int u, int p) {
    maximize(res, dp[u][0]);
    int dp0 = dp[u][0];
    int dp1 = dp[u][1];

    for (const auto &[v, w] : adj[u]) if (v != p) {
        dp[u][0] -= max(w + dp[v][1] , dp[v][0]);
        if (dp[v][0] + w - max(w + dp[v][1], dp[v][0]) == f[u][0])
            dp[u][1] = dp[u][0] + f[u][1];
        else dp[u][1] = dp[u][0] + f[u][0];
        
        dp[v][0] += max(w + dp[u][1], dp[u][0]);
        
        int val = dp[u][0] + w - max(w + dp[u][1], dp[u][0]);
        if (val > f[v][0]) f[v][1] = f[v][0], f[v][0] = val;
        else maximize(f[v][1], val);
        
        dp[v][1] = dp[v][0] + f[v][0];
        reroot(v, u);

        dp[u][0] = dp0;
        dp[u][1] = dp1;
    }
}

inline void solve(){   
    dfs_tree(1, -1);
    reroot(1, -1);
    cout << res << ln;
}

int main(){
    sinh_();
    io_faster
    file();
    int t = 1;
//    cin >> t;
    while (t--){
        readip();
        solve();
    }
}

Compilation message

beads.cpp: In function 'void readip()':
beads.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
beads.cpp:146:5: note: in expansion of macro 'REP'
  146 |     REP(i, 2, n) {
      |     ^~~
beads.cpp: In function 'void dfs_tree(int, int)':
beads.cpp:156:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  156 |     for (const auto &[v, w] : adj[u]) {
      |                      ^
beads.cpp: In function 'void reroot(int, int)':
beads.cpp:174:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  174 |     for (const auto &[v, w] : adj[u]) if (v != p) {
      |                      ^
beads.cpp: In function 'void file()':
beads.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
beads.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 3 ms 8024 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8024 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 2 ms 8028 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 3 ms 8024 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8024 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 2 ms 8028 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct
23 Correct 3 ms 8284 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 5 ms 8308 KB Output is correct
27 Correct 5 ms 8540 KB Output is correct
28 Correct 4 ms 8540 KB Output is correct
29 Correct 4 ms 8632 KB Output is correct
30 Correct 4 ms 8636 KB Output is correct
31 Correct 5 ms 8796 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8028 KB Output is correct
2 Correct 2 ms 8028 KB Output is correct
3 Correct 2 ms 8028 KB Output is correct
4 Correct 2 ms 8028 KB Output is correct
5 Correct 2 ms 8028 KB Output is correct
6 Correct 2 ms 8028 KB Output is correct
7 Correct 2 ms 8028 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 3 ms 8024 KB Output is correct
12 Correct 2 ms 8028 KB Output is correct
13 Correct 2 ms 8028 KB Output is correct
14 Correct 2 ms 8028 KB Output is correct
15 Correct 2 ms 8028 KB Output is correct
16 Correct 2 ms 8028 KB Output is correct
17 Correct 2 ms 8028 KB Output is correct
18 Correct 2 ms 8024 KB Output is correct
19 Correct 2 ms 8280 KB Output is correct
20 Correct 2 ms 8028 KB Output is correct
21 Correct 2 ms 8028 KB Output is correct
22 Correct 2 ms 8028 KB Output is correct
23 Correct 3 ms 8284 KB Output is correct
24 Correct 3 ms 8284 KB Output is correct
25 Correct 3 ms 8284 KB Output is correct
26 Correct 5 ms 8308 KB Output is correct
27 Correct 5 ms 8540 KB Output is correct
28 Correct 4 ms 8540 KB Output is correct
29 Correct 4 ms 8632 KB Output is correct
30 Correct 4 ms 8636 KB Output is correct
31 Correct 5 ms 8796 KB Output is correct
32 Correct 23 ms 10844 KB Output is correct
33 Correct 18 ms 10676 KB Output is correct
34 Correct 19 ms 10844 KB Output is correct
35 Correct 96 ms 19004 KB Output is correct
36 Correct 125 ms 19024 KB Output is correct
37 Correct 85 ms 19252 KB Output is correct
38 Correct 77 ms 19768 KB Output is correct
39 Correct 63 ms 19512 KB Output is correct
40 Correct 86 ms 19388 KB Output is correct
41 Correct 119 ms 22308 KB Output is correct