Submission #440404

#TimeUsernameProblemLanguageResultExecution timeMemory
440404sam571128Road Closures (APIO21_roads)C++17
5 / 100
124 ms11808 KiB
#include "roads.h" #include <bits/stdc++.h> #define ll long long using namespace std; vector<ll> minimum_closure_costs(int N, vector<int> U, vector<int> V, vector<int> W) { vector<vector<pair<int,int>>> adj; adj.resize(N); bool star = true, chain = true; int arr[N]; for(int i = 0;i < N-1;i++){ adj[U[i]].push_back({V[i],W[i]}); adj[V[i]].push_back({U[i],W[i]}); arr[U[i]+1] = W[i]; if(U[i]!=0) star = false; if(U[i]+1!=V[i]) chain = false; } vector<ll> cost(N,0); if(star){ sort(W.begin(),W.end()); ll now = 0; for(int i = 0;i < N-1;i++){ now += W[i]; cost[N-2-i] = now; } return cost; } if(chain){ ll dp[N][2] = {}, sum = 0; for(int i = 1;i <= N-1;i++){ dp[i][0] = dp[i-1][1]; dp[i][1] = dp[i-1][0]+arr[i]; sum += arr[i]; } cost[0] = sum, cost[1] = min(dp[N-1][0],dp[N-1][1]); return cost; } return cost; } //X 2 X 3 X 4 X 5 X
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...