| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 854450 | Wansur | Closing Time (IOI23_closing) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int mx=2e5+12;
vector<pair<int,long long>> g[mx];
long long d1[mx];
long long d2[mx];
int n,k;
void dfs(int v,int p,bool ok){
for(auto To:g[v]){
int to=To.f,w=To.s;
if(to==p){
continue;
}
if(ok){
d2[to]=d2[v]+w;
}
else{
d1[to]=d1[v]+w;
}
dfs(to,v,ok);
}
}
int max_score(int N, int x, int y, long long K, std::vector<int> U,std::vector<int> V, std::vector<int> W){
n=N,k=K;
for(int i=0;i<n;i++){
g[i].clear();
d1[i]=d2[i]=0;
}
for(int i=0;i<n-1;i++){
g[V[i]].push_back({U[i],W[i]});
g[U[i]].push_back({V[i],W[i]});
}
if(x>y){
swap(x,y);
}
dfs(x,-1,0);
dfs(y,-1,1);
long long sum=0,len=d1[y],ans=0,cnt=2*(y-x+1);
for(int i=x;i<=y;i++){
sum+=max(d1[i],d2[i]);
}
vector<long long> v;
for(int i=0;i<x;i++){
v.push_back(d1[i]);
}
for(int i=y+1;i<n;i++){
v.push_back(d2[i]);
}
sort(v.begin(),v.end());
for(int i=0;i<v.size();i++){
if(sum+v[i]<=k){
sum+=v[i];
cnt++;
}
}
if(sum<=k){
cnt+=min(n-(y-x+1),(k-sum)/len);
ans=cnt;
}
for(int pos=x;pos<y;pos++){
long long cnt=0,sum=0;
vector<long long> v;
for(int i=0;i<=pos;i++){
v.push_back(d1[i]);
}
for(int i=pos+1;i<n;i++){
v.push_back(d2[i]);
}
sort(v.begin(),v.end());
for(long long x:v){
if(sum+x<=k){
cnt++;
sum+=x;
}
}
ans=max(ans,cnt);
}
v.clear();
for(int i=0;i<n;i++){
v.push_back(d1[i]);
}
sort(v.begin(),v.end());
cnt=sum=0;
for(long long x:v){
if(sum+x<=k){
sum+=x;
cnt++;
}
}
ans=max(ans,cnt);
cnt=sum=0;
v.clear();
for(int i=0;i<n;i++){
v.push_back(d2[i]);
}
sort(v.begin(),v.end());
for(long long x:v){
if(sum+x<=k){
sum+=x;
cnt++;
}
}
ans=max(ans,cnt);
return ans;
}