Submission #1212425

#TimeUsernameProblemLanguageResultExecution timeMemory
1212425AvianshClosing Time (IOI23_closing)C++20
75 / 100
1072 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][n*2+1]; bool temp = 0; for(int i = 0;i<n;i++){ fill(dp[i],dp[i]+n*2+1,2e18); dp[i][0]=0; if(man[i]||temp){ dp[i][0]=2e18; temp = 1; } } dp[0][1]=cost1[0]; dp[0][2]=cost1[0]+cost2[0]; for(int i = 1;i<n;i++){ for(int j = 1;j<=2*n;j++){ if(man[i]){ //must take atleast one. dp[i][j]=dp[i-1][j-1]+cost1[i]; } else{ dp[i][j]=min({dp[i-1][j],dp[i-1][j-1]+cost1[i]}); } if(j>1){ dp[i][j]=min(dp[i][j],dp[i-1][j-2]+cost1[i]+cost2[i]); } dp[i][j]=min((long long)2e18,dp[i][j]); } } 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...