Submission #635962

#	Time	Username	Problem	Language	Result	Execution time	Memory
635962		daisy2	Race (IOI11_race)	C++17	31 / 100	393 ms	38780 KiB

race

#include<iostream>
#include "race.h"
#include<vector>
#include<algorithm>
using namespace std;
vector< pair<long long,long long> > v[200005];
long long numv[200005],nex,rs,k;
int ans=1000000000;
bool used[200005];
pair<long long,long long> pr[200005],nw[200005],r[200005];
long long numvr(long long vr,long long par)
{
    if(used[vr]) return 0;
    long long b=0;
    for(long long i=0;i<v[vr].size();i++)
    {
        if(v[vr][i].first==par) continue;
        b+=numvr(v[vr][i].first,vr);
    }
    return numv[vr]=b+1;
}
long long findcen(long long vr,long long par,long long ncom)
{
    if(used[vr]) return 0;
    for(long long i=0;i<v[vr].size();i++)
    {
        if(v[vr][i].first==par) continue;
        if(numv[v[vr][i].first]>(ncom/2)) return findcen(v[vr][i].first,vr,ncom);
    }
    return vr;
}
void finp(long long vr,long long par,long long d,long long br)
{
    if(used[vr]) return;
    nw[nex]={d,br};
    nex++;

    for(long long i=0;i<v[vr].size();i++)
    {
        if(v[vr][i].first!=par)
            finp(v[vr][i].first,vr,v[vr][i].second+d,br+1);
    }
}
void merg()
{
    long long in1=0,in2=0,i=0;

    while(in1<nex || in2<rs)
    {
        if(in2>=rs || (in1<nex && nw[in1].first<pr[in2].first) || (in1<nex && nw[in1].first==pr[in2].first && nw[in1].second<=pr[in2].second))
        {
            r[i]=nw[in1];
            in1++;i++;
        }
        else
        {
            r[i]=pr[in2];
            in2++;i++;
        }
    }
    for(long long j=0;j<i;j++)
        {pr[j]=r[j];}

    rs=i;
}
void calc()
{
    long long l,r,mid,fin;

    for(long long i=0;i<nex;i++)
    {
        l=0;r=rs-1;
        fin=k-nw[i].first;

        if(fin<0) break;
        if(fin>pr[r].first) continue;

        while(l<=r)
        {
            mid=(l+r)/2;

            if(pr[mid].first>=fin) r=mid-1;
            else l=mid+1;
        }
        if(pr[l].first==fin && pr[l].second+nw[i].second<ans)
            {ans=pr[l].second+nw[i].second;}
    }
}
void solve(long long cen)
{
    if(used[cen]) return;
    
    nex=0;rs=1;
    pr[0]={0,0};
    used[cen]=1;

    for(long long i=0;i<v[cen].size();i++)
    {
        if(used[v[cen][i].first]) continue;
        nex=0;
        finp(v[cen][i].first,cen,v[cen][i].second,1);

        if(nex==0) continue;
        sort(nw,nw+nex);

        calc();
        merg();
    }

    for(long long i=0;i<v[cen].size();i++)
    {
        if(used[v[cen][i].first]) continue;

        long long tn=numvr(v[cen][i].first,cen);
        solve(findcen(v[cen][i].first,cen,tn));
    }
}
int best_path (int N, int K, int H[][2], int L[])
{
    k=K;
    for(long long i=0;i<N-1;i++)
    {
        v[H[i][0]].push_back({H[i][1],L[i]});
        v[H[i][1]].push_back({H[i][0],L[i]});
    }
    long long tn=numvr(H[0][0],-1);
    solve(findcen(H[0][0],-1,tn));

    if(ans==1000000000) return -1;
  return ans;
}
/*
11 12
0 1 3
0 2 4
2 3 5
3 4 4
4 5 6
0 6 3
6 7 2
6 8 5
8 9 6
8 10 7
2
*/

Compilation message (stderr)

race.cpp: In function 'long long int numvr(long long int, long long int)':
race.cpp:15:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(long long i=0;i<v[vr].size();i++)
      |                       ~^~~~~~~~~~~~~
race.cpp: In function 'long long int findcen(long long int, long long int, long long int)':
race.cpp:25:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(long long i=0;i<v[vr].size();i++)
      |                       ~^~~~~~~~~~~~~
race.cpp: In function 'void finp(long long int, long long int, long long int, long long int)':
race.cpp:38:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for(long long i=0;i<v[vr].size();i++)
      |                       ~^~~~~~~~~~~~~
race.cpp: In function 'void solve(long long int)':
race.cpp:97:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(long long i=0;i<v[cen].size();i++)
      |                       ~^~~~~~~~~~~~~~
race.cpp:110:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(long long i=0;i<v[cen].size();i++)
      |                       ~^~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 0 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57