Submission #841711

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
841711	2023-09-01T23:32:53 Z	Pajaraja	Closing Time (IOI23_closing)	C++17	Compilation error	0 ms	0 KB

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;
    vector<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());
    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 i=0;i<put.size();i++)
    {
        int r=put[i].second;
        sum+=max(d[0][put[r]],d[1][put[r]])-d[1][put[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+1+lt);
    }
    return ans;
}

Compilation message

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:83:17: error: conflicting declaration 'std::vector<int> put'
   83 |     vector<int> put;
      |                 ^~~
closing.cpp:82:33: note: previous declaration as 'std::vector<std::pair<long long int, int> > put'
   82 |     vector<pair<long long,int>> put;
      |                                 ^~~
closing.cpp:86:19: error: 'aux' was not declared in this scope
   86 |     for(int i=0;i<aux.size();i++) put.push_back(aux[i].second);
      |                   ^~~
closing.cpp:89: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]
   89 |     for(int i=0;i<put.size();i++)
      |                 ~^~~~~~~~~~~
closing.cpp:92:9: error: 'sum' was not declared in this scope
   92 |         sum+=max(d[0][put[r]],d[1][put[r]])-d[1][put[r]];
      |         ^~~
closing.cpp:92:22: error: no match for 'operator[]' (operand types are 'long long int [200007]' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, int> >, std::pair<long long int, int> >::value_type' {aka 'std::pair<long long int, int>'})
   92 |         sum+=max(d[0][put[r]],d[1][put[r]])-d[1][put[r]];
      |                      ^
closing.cpp:92:35: error: no match for 'operator[]' (operand types are 'long long int [200007]' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, int> >, std::pair<long long int, int> >::value_type' {aka 'std::pair<long long int, int>'})
   92 |         sum+=max(d[0][put[r]],d[1][put[r]])-d[1][put[r]];
      |                                   ^
closing.cpp:92:49: error: no match for 'operator[]' (operand types are 'long long int [200007]' and '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, int> >, std::pair<long long int, int> >::value_type' {aka 'std::pair<long long int, int>'})
   92 |         sum+=max(d[0][put[r]],d[1][put[r]])-d[1][put[r]];
      |                                                 ^
closing.cpp:101:39: error: 'l' was not declared in this scope; did you mean 'lt'?
  101 |         ans=max(ans,(int)put.size()+r-l+1+lt);
      |                                       ^
      |                                       lt