Submission #635940

#	Time	Username	Problem	Language	Result	Execution time	Memory
635940		daisy2	Race (IOI11_race)	C++14	0 / 100	4 ms	4980 KiB

race

#include<iostream>
#include "race.h"
#include<vector>
#include<algorithm>
using namespace std;
vector< pair<int,int> > v[200005];
int numv[200005],nex,rs,k,ans=1000000000;
bool used[200005];
pair<int,int> pr[200005],nw[200005],r[200005];
int numvr(int vr,int par)
{
    if(used[vr]) return 0;
    int b=0;
    for(int 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;
}
int findcen(int vr,int par,int ncom)
{
    if(used[vr]) return 0;
    for(int 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(int vr,int par,int d,int br)
{
    if(used[vr]) return;
    nw[nex]={d,br};
    nex++;

    for(int 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()
{
    int in1=0,in2=0,i=0;

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

    rs=i;
}
void calc()
{

    int br=rs-1,l,r,mid,fin;

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

        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(int cen)
{
    if(used[cen]) return;
    nex=0;rs=1;
    pr[0]={0,0};
    used[cen]=1;

    for(int 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);
        sort(nw,nw+nex);

        calc();
        merg();
    }

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

        int 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(int 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]});
    }
    int tn=numvr(0,-1);
    solve(findcen(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 'int numvr(int, int)':
race.cpp:14:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for(int i=0;i<v[vr].size();i++)
      |                 ~^~~~~~~~~~~~~
race.cpp: In function 'int findcen(int, int, int)':
race.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<v[vr].size();i++)
      |                 ~^~~~~~~~~~~~~
race.cpp: In function 'void finp(int, int, int, int)':
race.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int i=0;i<v[vr].size();i++)
      |                 ~^~~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:93:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=0;i<v[cen].size();i++)
      |                 ~^~~~~~~~~~~~~~
race.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=0;i<v[cen].size();i++)
      |                 ~^~~~~~~~~~~~~~

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