Submission #79445

#TimeUsernameProblemLanguageResultExecution timeMemory
79445dualityChase (CEOI17_chase)C++11
100 / 100
552 ms250656 KiB
#define DEBUG 0 #include <bits/stdc++.h> using namespace std; #if DEBUG // basic debugging macros int __i__,__j__; #define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl #define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl #define printVar(n) cout<<#n<<": "<<n<<endl #define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl #define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;} #define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;} // advanced debugging class // debug 1,2,'A',"test"; class _Debug { public: template<typename T> _Debug& operator,(T val) { cout << val << endl; return *this; } }; #define debug _Debug(), #else #define printLine(l) #define printLine2(l,c) #define printVar(n) #define printArr(a,l) #define print2dArr(a,r,c) #define print2dArr2(a,r,c,l) #define debug #endif // define #define MAX_VAL 999999999 #define MAX_VAL_2 999999999999999999LL #define EPS 1e-6 #define mp make_pair #define pb push_back // typedef typedef unsigned int UI; typedef long long int LLI; typedef unsigned long long int ULLI; typedef unsigned short int US; typedef pair<int,int> pii; typedef pair<LLI,LLI> plli; typedef vector<int> vi; typedef vector<LLI> vlli; typedef vector<pii> vpii; typedef vector<plli> vplli; // ---------- END OF TEMPLATE ---------- int P[100000]; vi adjList[100000]; LLI sum[100000]; LLI dp[100000][101],dp2[100000][101]; int doDFS(int u,int p,int b) { int i,j; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) { doDFS(v,u,b); for (j = 0; j <= b; j++) { dp[u][j] = max(dp[u][j],dp[v][j]); if (j > 0) dp[u][j] = max(dp[u][j],dp[v][j-1]+sum[v]-P[u]); } } } return 0; } int doDFS2(int u,int p,int b) { int i,j; vi c; LLI m1[101],m2[101]; int p1[101]; for (i = 0; i < adjList[u].size(); i++) { int v = adjList[u][i]; if (v != p) c.pb(v); } for (i = 0; i <= b; i++) m1[i] = m2[i] = 0,p1[i] = -1; for (i = 0; i < c.size(); i++) { int v = c[i]; for (j = 0; j <= b; j++) { LLI x = dp[v][j]; if (j > 0) x = max(x,dp[v][j-1]+sum[v]-P[u]); if (x >= m1[j]) m2[j] = m1[j],m1[j] = x,p1[j] = i; else if (x >= m2[j]) m2[j] = x; } } for (i = 0; i < c.size(); i++) { int v = c[i]; for (j = 0; j <= b; j++) { dp2[v][j] = max(dp2[u][j],(i == p1[j]) ? m2[j]:m1[j]); if (j > 0) { dp2[v][j] = max(dp2[v][j],dp2[u][j-1]+sum[u]-P[v]); dp2[v][j] = max(dp2[v][j],((i == p1[j-1]) ? m2[j-1]:m1[j-1])+sum[u]-P[v]); } } doDFS2(v,u,b); } return 0; } int main() { int i; int n,v; int a,b; scanf("%d %d",&n,&v); for (i = 0; i < n; i++) scanf("%d",&P[i]); for (i = 1; i < n; i++) { scanf("%d %d",&a,&b); a--,b--; adjList[a].pb(b); adjList[b].pb(a); sum[a] += P[b],sum[b] += P[a]; } int j; LLI ans = 0; doDFS(0,-1,v); doDFS2(0,-1,v); for (i = 0; i < n; i++) { for (j = 0; j <= v; j++) { ans = max(ans,max(dp[i][j],dp2[i][j])); if (j < v) ans = max(ans,max(dp[i][j],dp2[i][j])+sum[i]); } } printf("%lld\n",ans); return 0; }

Compilation message (stderr)

chase.cpp: In function 'int doDFS(int, int, int)':
chase.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
chase.cpp: In function 'int doDFS2(int, int, int)':
chase.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
chase.cpp:86:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < c.size(); i++) {
                 ~~^~~~~~~~~~
chase.cpp:95:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < c.size(); i++) {
                 ~~^~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:112:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&v);
     ~~~~~^~~~~~~~~~~~~~~
chase.cpp:113:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < n; i++) scanf("%d",&P[i]);
                             ~~~~~^~~~~~~~~~~~
chase.cpp:115:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...