Submission #104952

#TimeUsernameProblemLanguageResultExecution timeMemory
104952eriksuenderhaufChase (CEOI17_chase)C++11
100 / 100
500 ms253048 KiB
#pragma GCC optimize("O3") #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #define enl printf("\n") #define case(t) printf("Case #%d: ", (t)) #define ni(n) scanf("%d", &(n)) #define nl(n) scanf("%lld", &(n)) #define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i]) #define nal(a, n) for (int i = 1; i <= (n); i++) nl(a[i]) #define pri(n) printf("%d\n", (n)) #define prl(n) printf("%lld\n", (n)) #define pii pair<int, int> #define pll pair<long long, long long> #define vii vector<pii> #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef cc_hash_table<int,int,hash<int>> ht; const double pi = acos(-1); const int MOD = 1e9 + 7; const int INF = 1e9 + 7; const int MAXN = 1e5 + 5; const double eps = 1e-9; vi adj[MAXN]; ll p[MAXN], dp[2][MAXN][101], ans = 0, sum[MAXN]; int vv; void dfs(int u, int pa) { ll sm = sum[u] - p[pa];; ll m1[101] = {0}, m2[101] = {0}; dp[0][u][0] = dp[1][u][0] = 0; dp[1][u][1] = sm + p[pa]; for (int v: adj[u]) if (v != pa) { dfs(v, u); for (int i = 1; i <= vv; i++) { dp[0][u][i] = max(dp[0][u][i], max(dp[0][v][i], dp[0][v][i - 1] + sm)); dp[1][u][i] = max(dp[1][u][i], max(dp[1][v][i], dp[1][v][i - 1] + sm + p[pa] - p[v])); if (dp[0][v][i] >= m1[i]) m2[i] = m1[i], m1[i] = dp[0][v][i]; else if (dp[0][v][i] > m2[i]) m2[i] = dp[0][v][i]; } } for (int v: adj[u]) { if (v == pa) continue; if (vv > 0) ans = max(ans, sm + p[pa] + dp[0][v][vv - 1]); for (int i = 0; i <= vv; i++) { ll x = max(dp[1][v][i], i == 0 ? 0 : dp[1][v][i - 1] + sm + p[pa] - p[v]); if (m1[vv - i] == dp[0][v][vv - i]) ans = max(ans, x + m2[vv - i]); else ans = max(ans, x + m1[vv - i]); } } } int main() { int n; ni(n), ni(vv); nal(p, n); for (int i = 1; i < n; i++) { int u, v; ni(u), ni(v); adj[u].pb(v); adj[v].pb(u); sum[u] += p[v], sum[v] += p[u]; } dfs(1, 0); prl(ans); return 0; }

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(vv);
          ^
chase.cpp:71:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
chase.cpp:8:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define nl(n) scanf("%lld", &(n))
               ~~~~~^~~~~~~~~~~~~~
chase.cpp:10:50: note: in expansion of macro 'nl'
 #define nal(a, n) for (int i = 1; i <= (n); i++) nl(a[i])
                                                  ^~
chase.cpp:72:5: note: in expansion of macro 'nal'
     nal(p, n);
     ^~~
chase.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ni(u), ni(v);
              ^
chase.cpp:76:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...