Submission #101616

#TimeUsernameProblemLanguageResultExecution timeMemory
101616cheehengChase (CEOI17_chase)C++14
0 / 100
103 ms27316 KiB
#include <bits/stdc++.h> using namespace std; long long p[100005]; long long p2[100005]; vector<int> AdjList[100005]; int parent[100005]; vector<int> AdjList2[100005]; int dist[100005]; long long memo[1005][105][2]; long long dp(int u, int b, bool taken){ if(AdjList2[u].empty()){ // leaf node if(b >= 1 && !taken && parent[u] != -1){ return p[parent[u]]; }else{ return 0; } }else if(b == 0){ return 0; }else if(memo[u][b][taken] != -1){ return memo[u][b][taken]; }else{ long long temp = 0; long long score = 0; for(int v: AdjList2[u]){ score += p[v]; } if(!taken && parent[u] != -1){ score += p[parent[u]]; } for(int v: AdjList2[u]){ temp = max(temp, score+dp(v, b-1, 1)); temp = max(temp, dp(v, b-1, 0)); } return memo[u][b][taken] = temp; } } int main(){ int N, v; scanf("%d%d", &N, &v); for(int i = 1; i <= N; i ++){ scanf("%d", &p[i]); p2[i] = p[i]; } for(int i = 1; i < N; i ++){ int a, b; scanf("%d%d", &a, &b); AdjList[a].push_back(b); AdjList[b].push_back(a); } long long ans = 0; for(int i = 1; i <= N; i ++){ queue<int> q; q.push(i); memset(dist, -1, sizeof(dist)); dist[i] = 0; for(int j = 1; j <= N; j ++){ AdjList2[j].clear(); } while(!q.empty()){ int u = q.front(); q.pop(); for(int v: AdjList[u]){ if(dist[v] == -1){ dist[v] = dist[u] + 1; parent[v] = u; AdjList2[u].push_back(v); q.push(v); } } } memset(memo, -1, sizeof(memo)); long long temp = dp(i, v, 1); ans = max(ans, temp); } printf("%lld", ans); return 0; }

Compilation message (stderr)

chase.cpp: In function 'int main()':
chase.cpp:52:26: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d", &p[i]);
                     ~~~~~^
chase.cpp:49: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:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
         ~~~~~^~~~~~~~~~~~~
chase.cpp:58: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...