Submission #636470

#	Time	Username	Problem	Language	Result	Execution time	Memory
636470		daisy2	Race (IOI11_race)	C++14	100 / 100	888 ms	48344 KiB

race

#include<iostream>
#include "race.h"
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
vector< pair<long long,long long> > v[200005];
long long numv[200005],nex,rs,k;
long long ans=10000000000000;
bool used[200005];
map<long long,long long> mp;
pair<long long,long long> nw[200005];
long long numvr(long long vr,long long par)
{
    if(used[vr]) return numv[vr]=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 -1;
    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 calc()
{
    for(int i=0;i<nex;i++)
    {
       if(mp.count(k-nw[i].first))
            ans=min(ans,(mp[k-nw[i].first]+nw[i].second));
    }
    for(int i=0;i<nex;i++)
    {
       if(mp.count(nw[i].first))
            mp[nw[i].first]=min(mp[nw[i].first],nw[i].second);
       else
        mp[nw[i].first]=nw[i].second;
    }
}
void solve(long long cen)
{
    if(used[cen]) return;

    mp.clear();
    mp[0]=0;

    nex=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);

        calc();
    }

    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==10000000000000) 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:17: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]
   17 |     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:27: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]
   27 |     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:40: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]
   40 |     for(long long i=0;i<v[vr].size();i++)
      |                       ~^~~~~~~~~~~~~
race.cpp: In function 'void solve(long long int)':
race.cpp:71: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]
   71 |     for(long long i=0;i<v[cen].size();i++)
      |                       ~^~~~~~~~~~~~~~
race.cpp:80: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]
   80 |     for(long long i=0;i<v[cen].size();i++)
      |                       ~^~~~~~~~~~~~~~

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