Submission #885176

#TimeUsernameProblemLanguageResultExecution timeMemory
885176nasamChase (CEOI17_chase)C++17
0 / 100
209 ms265724 KiB
/************************************* * author: Pham Huy Khanh * *************************************/ #include <bits/stdc++.h> #define ll long long #define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++) #define FOD(i,b,a) for (int i = (b), _a = (a); i >= _a; i--) #define FORE(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); i++) #define ALL(v) (v).begin(), (v).end() #define BIT(x, i) (((x) >> (i)) & 1) #define MASK(i) (1LL << (i)) #define CNTBIT(x) __builtin_popcount(x) #define fi first #define se second #define pb push_back #define eb emplace_back #define left ___left #define right ___right #define pii pair<int, int> #define pll pair<ll, ll> #define DEBUG(n, a) FOR (i, 1, n) cout << a[i] << ' '; cout << endl; #define lob lower_bound // >= #define upb upper_bound // > #define endl "\n" #define NAME "main" using namespace std; template<class X, class Y> bool maximize(X &x, Y y){ if (x < y){ x = y; return true; } return false; } template<class X, class Y> bool minimize(X &x, Y y){ if (x > y){ x = y; return true; } return false; } #define gogobruhbruh ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); #define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); } const int MOD = 998244353; void add(int &a, int b){ if ((a += b) >= MOD) a -= MOD; } void sub(int &a, int b){ if ((a -= b) < 0) a += MOD; } int muti(int a, int b){ return (1LL * a * b) % MOD; } int Pow(int x, int y){ int res = 1; for (; y; y >>= 1){ if (y & 1) res = muti(res, x); x = muti(x, x); } return res; } const int MAX = 1e5 + 7; const int LIM = 1e2 + 7; const ll INF = 1e18 + 7; int num, lim; int val[MAX]; ll dp[MAX][LIM][2], dp2[MAX][LIM]; vector<int> edge[MAX]; void dfs(int u, int pre){ for (int v : edge[u]){ if (v == pre) continue; dfs(v, u); FOR (i, 2, lim){ ll tmp = dp[v][i - 1][0] + dp[u][1][0] - val[v]; if (tmp > dp[u][i][0]) dp[u][i][1] = dp[u][i][0], dp[u][i][0] = tmp; else maximize(dp[u][i][1], tmp); } } } void dfs2(int u, int pre){ for (int v : edge[u]){ if (v == pre) continue; FOR (i, 1, lim){ dp2[v][i + 1] = dp2[u][i] + dp[v][1][0] - val[u]; ll tmp = dp[v][i - 1][0] + dp[u][1][0] - val[v]; if (dp[u][i][0] == tmp) maximize(dp2[v][i + 1], dp[u][i][1] + dp[v][1][0] - val[u]); else maximize(dp2[v][i + 1], dp[u][i][0] + dp[v][1][0] - val[u]); } dfs2(v, u); } } void solve(){ dfs(1, -1); dfs2(1, -1); ll res = 0; FOR (u, 1, num) FOR (i, 1, lim) maximize(res, max(dp[u][i][0], dp2[u][i])); cout << res; } void read(){ cin >> num >> lim; FOR (i, 1, num) cin >> val[i]; FOR (i, 2, num){ static int u, v; cin >> u >> v; edge[u].eb(v); edge[v].eb(u); dp[u][1][0] += val[v]; dp[v][1][0] += val[u]; } } int main(){ gogobruhbruh; file("main"); int test = 1; // cin >> test; while (test--) read(), solve(); }

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:33:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:109:5: note: in expansion of macro 'file'
  109 |     file("main");
      |     ^~~~
chase.cpp:33:95: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 | #define  file(name)  if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
      |                                                                                       ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
chase.cpp:109:5: note: in expansion of macro 'file'
  109 |     file("main");
      |     ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...