Submission #978336

#	Time	Username	Problem	Language	Result	Execution time	Memory
978336		simona1230	Race (IOI11_race)	C++17	21 / 100	3047 ms	59452 KiB

race

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

int n,k;
vector<int> v[200001];
vector<int> w[200001];
map<int,int> mp[200001];
int sz[200001];
int used[200001];
int ans,cent;

void dfs(int i,int p)
{
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j],wg=w[i][j];
        if(nb==p||used[nb])continue;

        dfs(nb,i);
        //cout<<nb<<" --- "<<wg<<endl;
        if(i==cent)
        {
            for(auto it=mp[nb].begin(); it!=mp[nb].end(); it++)
            {
                int vl=it->first+wg;
                int cnt=it->second+1;
                if(mp[i].find(k-vl)!=mp[i].end())
                {
                    //if(mp[i][k-vl]+cnt<30)cout<<i<<" - "<<k-vl<<" - "<<vl<<" "<<mp[i][k-vl]+cnt<<" "<<mp[i][k-vl]<<" "<<cnt<<endl;
                    ans=min(ans,mp[i][k-vl]+cnt);
                }
            }
            if(mp[i].find(k-wg)!=mp[i].end())
                ans=min(ans,mp[i][k-wg]+1);
        }
        for(auto it=mp[nb].begin(); it!=mp[nb].end(); it++)
        {
            int vl=it->first+wg;
            int cnt=it->second+1;
            if(vl==k)
            {
                //cout<<cnt<<endl;
                ans=min(ans,cnt);
            }
            mp[i][vl]=min(mp[i][vl],cnt);
            if(mp[i][vl]==0)mp[i][vl]=cnt;
            //cout<<i<<"->"<<vl<<" "<<mp[i][vl]<<" "<<it->first<<" "<<it->second<<endl;
        }

        mp[i][wg]=1;
        if(wg==k)ans=1;
        mp[nb].clear();
    }
    //for(auto it=mp[i].begin();it!=mp[i].end();it++)
    //    cout<<i<<" * "<<it->first<<" * "<<it->second<<endl;
}


void calc(int i,int p)
{
    //cout<<i<<endl;
    sz[i]=1;
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(nb==p||used[nb])continue;

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

int centroid(int i,int p)
{
    //cout<<"in "<<i<<endl;
    for(int j=0; j<v[i].size(); j++)
    {
        int nb=v[i][j];
        if(nb==p||used[nb])continue;
        if(sz[nb]>n/2)return centroid(nb,i);
    }
    return i;
}

void solve(int i)
{
    //cout<<i<<endl;
    calc(i,n);
    int c=centroid(i,n);
    cent=c;
    ///cout<<"* "<<c<<endl;

    dfs(c,n);
    used[c]=1;
    for(int j=0; j<v[c].size(); j++)
    {
        int nb=v[c][j];
        if(!used[nb])solve(nb);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    ans=n;
    for(int i=0; i<n-1; i++)
    {
        v[H[i][0]].push_back(H[i][1]);
        v[H[i][1]].push_back(H[i][0]);
        w[H[i][0]].push_back(L[i]);
        w[H[i][1]].push_back(L[i]);
        //cout<<H[i][0]<<" "<<H[i][1]<<endl;
    }

    /*for(int i=0;i<n;i++)
    {
        cout<<i<<" ";
        for(int j=0;j<v[i].size();j++)
            cout<<v[i][j]<<"/"<<w[i][j]<<" ";
        cout<<endl;
    }*/

    solve(0);
    if(ans==n)ans=-1;
    return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:15:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
race.cpp: In function 'void calc(int, int)':
race.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int j=0; j<v[i].size(); j++)
      |                  ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(int j=0; j<v[c].size(); j++)
      |                  ~^~~~~~~~~~~~

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