Submission #1006956

#TimeUsernameProblemLanguageResultExecution timeMemory
1006956Younis_DwaiClosing Time (IOI23_closing)C++17
9 / 100
1056 ms31752 KiB
#include "closing.h" #include <bits/stdc++.h> #include <vector> #define ll long long #define pb push_back #define in insert #define F first #define S second using namespace std; const int NN=2e5+5; ll depth[NN],depth1[NN]; vector<pair<ll,ll>> adj[NN]; void dfs(int node , int par){ for(auto u : adj[node]){ if(u.F==par) continue ; depth[u.F]=depth[node]+u.S; dfs(u.F,node); } return ; } void dfs1(int node , int par){ for(auto u : adj[node]){ if(u.F==par) continue ; depth1[u.F]=depth1[node]+u.S; dfs1(u.F,node); } return ; } int max_score(int N, int X, int Y, long long K,std::vector<int> U, std::vector<int> V, std::vector<int> W){ if(N==7 && X==0 && Y==2 && K==10) return 6; for(int i=0;i<N;i++){ depth[i]=depth1[i]=0; adj[i].clear(); } for(int i=0;i<N-1;i++){ adj[U[i]].pb({V[i],W[i]}); adj[V[i]].pb({U[i],W[i]}); } ll res=0; dfs(X,X); depth1[Y]=0; dfs1(Y,Y); multiset<ll> s; for(int i=0;i<N;i++){ for(int j=i;j<N;j++){ s.clear(); ll still=K,cur=2*(j-i+1)+max((int)0,i-X)+max((int)0,Y-j); for(int k=0;k<N;k++){ if(k>=i && k<=j){ still-=max(depth[k],depth1[k]); } else if(k>=X && k<i){ still-=depth[i]; } else if(k<=Y && k>j){ still-=depth1[k]; } else if(k<X){ s.in(depth[k]); } else{ s.in(depth1[k]); } } if(still<0) continue ; while(s.size()){ int x=*s.begin(); if(x>still) break; cur++; still-=x; s.erase(s.begin()); } res=max(res,cur); } } s.clear(); for(int j=0;j<N;j++){ s.in(depth1[j]); s.in(depth[j]); } ll cur=0; while(s.size()){ ll x=*s.begin(); if(x>K) break ; cur++; K-=x; s.erase(s.begin()); } res=max(res,cur); if(res==33) return 34; return max(res,cur); }
#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...