Submission #841691

#	Time	Username	Problem	Language	Result	Execution time	Memory
841691		Pajaraja	Closing Time (IOI23_closing)	C++17	8 / 100	191 ms	54860 KiB

closing

#include "closing.h"
#include <bits/stdc++.h>
#include <vector>
#define MAXN 200007
using namespace std;
vector<int> g[MAXN],w[MAXN];
long long d[2][MAXN];
long long pm[2*MAXN];
void dfs(int br,int s,int f,long long dist)
{
    d[br][s]=dist;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(br,g[s][i],s,dist+w[s][i]);
}
int max_score(int N, int X, int Y, long long K, std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    for(int i=0;i<N;i++) g[i].clear();
    for(int i=0;i<N;i++) w[i].clear();
    for(int i=0;i<N-1;i++)
    {
        g[U[i]].push_back(V[i]);
        g[V[i]].push_back(U[i]);
        w[U[i]].push_back(W[i]);
        w[V[i]].push_back(W[i]);
    }
    if(X>Y) swap(X,Y);
    dfs(0,X,X,0);
    dfs(1,Y,Y,0);
    vector<long long> vk;
    long long total=0;
    int br=0,ans;
    for(int i=0;i<N;i++) vk.push_back(d[0][i]);
    for(int i=0;i<N;i++) vk.push_back(d[1][i]);
    sort(vk.begin(),vk.end());
    for(int i=0;i<vk.size();i++)
    {
        if(total+vk[i]<=K)
        {
            total+=vk[i];
            br++;
        }
    }
    ans=br;
    vector<long long> p;
    vector<pair<long long,long long> > v;
    for(int i=0;i<N;i++) if(d[0][i]+d[1][i]!=d[0][Y])
    {
        int a=min(d[0][i],d[1][i]),b=max(d[0][i],d[1][i]);
        if(2*a<=b)
        {
            v.push_back({2*a,0});
            v.push_back({2*(b-a),0});
        }
        else v.push_back({b,-a});
    }
    sort(v.begin(),v.end());
    p.push_back(0);
    if(v.size()!=0)
    {
        long long pmin=1000000000000000000LL;
        for(int i=v.size()-1;i>=0;i--)
        {
            if(v[i].second!=0) pmin=min(pmin,-v[i].second);
            pm[i]=pmin;
        }
        for(int i=0;i<v.size();i++)
        {
            if(!v[i].second) p.push_back(p.back()+v[i].first/2);
            else
            {
                long long cur=p.back();
                p.push_back(cur+pm[i]);
                p.push_back(cur+v[i].first);
            }
        }
    }
    vector<pair<int,int>> aux;
    vector<int> put;
    for(int i=0;i<N;i++) if(d[0][i]+d[1][i]==d[0][Y]) aux.push_back({d[0][i],i});
    sort(aux.begin(),aux.end());
    /*for(int i=0;i<aux.size();i++) put.push_back(aux[i].second);
    for(int i=0;i<p.size();i++) cout<<p[i]<<" ";*/
    cout<<endl;
    for(int l=0;l<put.size();l++)
    {
        long long sum=0;
        for(int i=X;i<l;i++) sum+=d[0][put[i]];
        for(int i=l;i<=Y;i++) sum+=d[1][put[i]];
        int lt=0,rt=p.size()-1;
        for(int r=l;r<=put.size();r++)
        {
            int lt=0,rt=p.size()-1;
            if(sum>K) continue;
            while(lt!=rt)
            {
                int s=(lt+rt+1)/2;
                if(p[s]+sum>K) rt=s-1;
                else lt=s;
            }
            ans=max(ans,(int)put.size()+r-l+lt);
            if(r<put.size()) sum+=max(d[0][put[r]],d[1][put[r]])-d[1][put[r]];
        }
    }
    return ans;
}

Compilation message (stderr)

closing.cpp: In function 'void dfs(int, int, int, long long int)':
closing.cpp:12:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(br,g[s][i],s,dist+w[s][i]);
      |                 ~^~~~~~~~~~~~
closing.cpp: In function 'int max_score(int, int, int, long long int, std::vector<int>, std::vector<int>, std::vector<int>)':
closing.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for(int i=0;i<vk.size();i++)
      |                 ~^~~~~~~~~~
closing.cpp:65:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i=0;i<v.size();i++)
      |                     ~^~~~~~~~~
closing.cpp:83:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int l=0;l<put.size();l++)
      |                 ~^~~~~~~~~~~
closing.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         for(int r=l;r<=put.size();r++)
      |                     ~^~~~~~~~~~~~
closing.cpp:100:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             if(r<put.size()) sum+=max(d[0][put[r]],d[1][put[r]])-d[1][put[r]];
      |                ~^~~~~~~~~~~
closing.cpp:88:13: warning: unused variable 'lt' [-Wunused-variable]
   88 |         int lt=0,rt=p.size()-1;
      |             ^~
closing.cpp:88:18: warning: unused variable 'rt' [-Wunused-variable]
   88 |         int lt=0,rt=p.size()-1;
      |                  ^~

• Subtask 0: 0 / 0
• Subtask 1: 8 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 9
• Subtask 6: 0 / 11
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 17