Submission #841713

#	Time	Username	Problem	Language	Result	Execution time	Memory
841713		Pajaraja	Closing Time (IOI23_closing)	C++17	100 / 100	221 ms	57000 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])
    {
        long long 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);
            else pmin=min(pmin,v[i].first/2);
            pm[i]=pmin;
        }
        long long last=0;
        for(int i=0;i<v.size();i++)
        {
            if(!v[i].second)
            {
                p.push_back(p.back()+v[i].first/2);
                last=v[i].first/2;
            }
            else
            {
                long long cur=p.back();
                p.push_back(min(cur+pm[i],cur-last+v[i].first));
                p.push_back(cur+v[i].first);
            }
        }
    }
    vector<pair<long long,int>> put;
    for(int i=0;i<N;i++) if(d[0][i]+d[1][i]==d[0][Y]) put.push_back({abs(d[0][i]-d[1][i]),i});
    sort(put.begin(),put.end());
    long long sum=0;
    for(int i=0;i<put.size();i++) sum+=min(d[0][put[i].second],d[1][put[i].second]);
    for(int i=0;i<put.size();i++)
    {
        int r=put[i].second;
        sum+=max(d[0][r],d[1][r])-min(d[0][r],d[1][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()+i+1+lt);
    }
    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:67: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]
   67 |         for(int i=0;i<v.size();i++)
      |                     ~^~~~~~~~~
closing.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for(int i=0;i<put.size();i++) sum+=min(d[0][put[i].second],d[1][put[i].second]);
      |                 ~^~~~~~~~~~~
closing.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<put.size();i++)
      |                 ~^~~~~~~~~~~

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