Submission #1078418

#TimeUsernameProblemLanguageResultExecution timeMemory
1078418vjudge1Closing Time (IOI23_closing)C++17
0 / 100
41 ms10064 KiB
#include "closing.h" #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); #define vi vector<int> #define ll long long #define ff first #define ss second using namespace std; const int MAX=3e3+5; vector<pair<int,int>> v[MAX]; ll maxi=0; ll D[MAX]; ll X[MAX]; ll Y[MAX]; ll R[MAX]; ll A[MAX]; bool vis[MAX][MAX]; void dfs(int u,int p){ for(auto it:v[u]){ if(it.ff==p) continue; D[it.ff]=D[u]+it.ss; dfs(it.ff,u); } } int max_score(int n,int x,int y, ll k,vi u,vi l, vi w){ for(int i=0;i<n-1;i++){ v[u[i]].push_back({l[i],w[i]}); v[l[i]].push_back({u[i],w[i]}); } maxi=k; D[x]=0; dfs(x,-1); for(int i=0;i<n;i++){ X[i]=D[i]; } D[y]=0; dfs(y,-1); for(int i=0;i<n;i++){ Y[i]=D[i]; } int res=0; for(int i=0;i<n;i++){ for(int j=i;j<n;j++){ fill(A,A+n,0); ll peso=0; int ans=0; for(int k=x;k<i;k++){ A[k]=X[k]; ans++; } for(int k=i;k<x;k++){ A[k]=X[k]; ans++; } for(int k=j;k<y;k++){ A[k]=max(Y[k],A[k]); ans++; } for(int k=y;k<j;k++){ A[k]=max(Y[k],A[k]); ans++; } for(int k=i;k<=j;k++){ A[k]=max(Y[k],X[k]); ans+=2; } multiset<ll>s; for(int k=0;k<n;k++){ if(A[k]){ peso+=A[k]; } else s.insert(min(X[k],Y[k])); } for(auto it:s){ if(peso+ it<=maxi){ peso+=it; ans++; } } if(peso>maxi) continue; else res=max(res,ans); } } fill(A,A+n,0); multiset<ll>s; for(int k=0;k<n;k++){ s.insert(min(X[k],Y[k])); } ll peso=0; int ans=0; for(auto it:s){ if(peso+ it<=maxi){ peso+=it; ans++; } } for(int i=0;i<n;i++){ v[i].clear(); } return max(res,ans); }
#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...