Submission #1090492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090492		simona1230	Race (IOI11_race)	C++17	100 / 100	331 ms	49480 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> v[200001],w[200001];
int ans=200000;

void add(int i,int j,int k)
{
    v[i].push_back(j);
    v[j].push_back(i);
    w[i].push_back(k);
    w[j].push_back(k);
}

int n,k;

int all;
int sz[200001];
int mark[200001];

void prec(int i,int p)
{
    sz[i]=1;
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||mark[nb])continue;

        prec(nb,i);
        sz[i]+=sz[nb];
    }
}

int centroid(int i,int p)
{
    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||mark[nb])continue;

        if(sz[nb]>all/2)return centroid(nb,i);
    }

    return i;
}

int mp[1000001];
vector<int> val;
vector<pair<int,int> > ext;

void dfs(int i,int p,int cnt,int wg)
{
    if(wg>k)return;

    if(wg==k)ans=min(ans,cnt);
    else
    {
        int wg2=k-wg;
        //cout<<wg2<<" + "<<mp[wg2]<<endl;
        ans=min(ans,cnt+mp[wg2]);
    }

    //cout<<i<<" "<<wg<<endl;

    ext.push_back({wg,cnt});

    for(int j=0;j<v[i].size();j++)
    {
        int nb=v[i][j];
        if(nb==p||mark[nb])continue;

        dfs(nb,i,cnt+1,wg+w[i][j]);
    }
}

void solve(int beg)
{
    prec(beg,-1);
    all=sz[beg];
    //cout<<all<<endl;
    int c=centroid(beg,-1);
    //cout<<"! "<<c<<endl;

    for(int i=0;i<val.size();i++)
        mp[val[i]]=n;
    val.clear();
    mark[c]=1;

    for(int i=0;i<v[c].size();i++)
    {
        int nb=v[c][i];
        if(mark[nb])continue;

        //cout<<c<<" "<<nb<<endl;
        dfs(nb,-1,1,w[c][i]);

        for(int j=0;j<ext.size();j++)
        {
            //cout<<"= "<<ext[j].first<<endl;
            if(mp[ext[j].first]==n)val.push_back(ext[j].first);
            mp[ext[j].first]=min(mp[ext[j].first],ext[j].second);
        }
        ext.clear();
    }

    for(int i=0;i<v[c].size();i++)
    {
        int nb=v[c][i];
        if(!mark[nb])solve(nb);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;

    for(int i=1;i<=k;i++)
        mp[i]=n;

    for(int i=0;i<n-1;i++)
        add(H[i][0],H[i][1],L[i]);

    solve(0);

    if(ans>=n)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 'void prec(int, int)':
race.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void dfs(int, int, int, int)':
race.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i=0;i<val.size();i++)
      |                 ~^~~~~~~~~~~
race.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<v[c].size();i++)
      |                 ~^~~~~~~~~~~~
race.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int j=0;j<ext.size();j++)
      |                     ~^~~~~~~~~~~
race.cpp:107:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |     for(int i=0;i<v[c].size();i++)
      |                 ~^~~~~~~~~~~~

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