Submission #987039

#TimeUsernameProblemLanguageResultExecution timeMemory
987039activedeltorreClosing Time (IOI23_closing)C++17
8 / 100
160 ms43540 KiB
#include "closing.h" #include <queue> using namespace std; #include <vector> #include <iostream> long long dist[200005][4]; vector<pair<long long,long long> >adj[200005]; void dfs(long long curr,long long par,long long tip) { for(auto k:adj[curr]) { if(k.first!=par) { dist[k.first][tip]=dist[curr][tip]+k.second; dfs(k.first,curr,tip); } } } priority_queue<long long>pq; int max_score(int N, int X, int Y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W) { long long n=N,x,y,i,w; for(i=0; i<=n; i++) { adj[i].clear(); } for(i=0; i<n-1; i++) { x=U[i]; y=V[i]; w=W[i]; adj[x].push_back({y,w}); adj[y].push_back({x,w}); } if(X>Y) { swap(X,Y); } x=X; y=Y; dist[x][0]=0; dist[y][1]=0; dfs(x,-1,0); dfs(y,-1,1); if(dist[y][0]>2*K) { for(i=0; i<n; i++) { pq.push(-dist[i][0]); pq.push(-dist[i][1]); } long long cnt=0; while(pq.size()) { if(K>-pq.top()) { cnt++; K+=pq.top(); } pq.pop(); } return cnt; } else { long long st,dr; int sol=0; for(st=0; st<=y; st++) { for(dr=x; dr<n; dr++) { long long sum=0; int cnt=0; for(i=st; i<=dr; i++) { sum-=min(dist[i][0],dist[i][1]); } for(i=x;i<=dr;i++) { sum+=dist[i][0]; cnt++; } for(i=y;i>=st;i--) { sum+=dist[i][1]; cnt++; } cnt+=max(0LL,x-st); cnt+=max(0LL,dr-y); if(sum<=K) { for(i=min(x-1,st-1); i>=0; i--) { pq.push(-dist[i][0]); } for(i=max(y+1,dr+1); i<n; i++) { pq.push(-dist[i][1]); } while(pq.size()) { if(sum-pq.top()<=K) { sum-=pq.top(); cnt++; } pq.pop(); } sol=max(sol,cnt); } } } return sol; } return 0; }
#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...