Submission #1212429

#TimeUsernameProblemLanguageResultExecution timeMemory
1212429AvianshClosing Time (IOI23_closing)C++20
75 / 100
1089 ms2162688 KiB
#include "closing.h" #include <vector> #include <bits/stdc++.h> using namespace std; void dfs(int st, vector<array<int,2>>g[], int p, long long dist[], long long d){ dist[st]=d; for(array<int,2>e:g[st]){ if(e[0]==p) continue; dfs(e[0],g,st,dist,d+e[1]); } } vector<int>xypath; void dfsxy(int st, vector<array<int,2>>g[], int p, vector<int>&path, int y){ path.push_back(st); if(st==y){ xypath.clear(); for(int i : path){ xypath.push_back(i); } } for(array<int,2>e : g[st]){ if(e[0]==p) continue; dfsxy(e[0],g,st,path,y); } path.pop_back(); } int max_score(int n, int x, int y, long long k, vector<int> u, vector<int> v, vector<int> w) { vector<array<int,2>>g[n]; int m = u.size(); for(int i = 0;i<m;i++){ g[u[i]].push_back({v[i],w[i]}); g[v[i]].push_back({u[i],w[i]}); } long long distx[n], disty[n]; dfs(x,g,-1,distx,0); dfs(y,g,-1,disty,0); long long cost1[n],cost2[n]; for(int i = 0;i<n;i++){ cost1[i]=min(distx[i],disty[i]); cost2[i]=max(distx[i],disty[i])-cost1[i]; } vector<int>pt; dfsxy(x,g,-1,pt,y); //case 1: int ans1 = 0; //only till level 1. priority_queue<long long,vector<long long>,greater<long long>>pq; for(int i = 0;i<n;i++){ pq.push(cost1[i]); } long long curk = 0; while(curk<=k&&pq.size()){ long long a = pq.top(); pq.pop(); if(curk+a>k) break; ans1++; curk+=a; } //case 2: bool man[n]; fill(man,man+n,0); for(int i : xypath){ man[i]=1; } long long dp[n][2 * n + 1]; for (int j = 0; j <= 2 * n; j++) dp[0][j] = 2e18; if (man[0]) { dp[0][0] = 2e18; // must take at least 1 } else { dp[0][0] = 0; } dp[0][1] = cost1[0]; dp[0][2] = cost1[0] + cost2[0]; for (int i = 1; i < n; i++) { for (int j = 0; j <= 2 * n; j++) dp[i][j] = 2e18; for (int j = 0; j <= 2 * n; j++) { if (dp[i-1][j] == 2e18) continue; // Take 0 items from bag i if (!man[i]) { dp[i][j] = min(dp[i][j], dp[i-1][j]); } // Take 1 item from bag i if (j + 1 <= 2 * n) dp[i][j+1] = min(dp[i][j+1], dp[i-1][j] + cost1[i]); // Take 2 items from bag i if (j + 2 <= 2 * n) dp[i][j+2] = min(dp[i][j+2], dp[i-1][j] + cost1[i] + cost2[i]); } } int ans2 = 0; for (int j = 0; j <= 2 * n; j++) { if (dp[n-1][j] <= k) { ans2 = max(ans2, j); } } return max(ans1,ans2); }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...