Submission #978020

#	Time	Username	Problem	Language	Result	Execution time	Memory
978020		simona1230	Race (IOI11_race)	C++17	0 / 100	176 ms	262144 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=n;

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);
        for(auto it=mp[nb].begin();it!=mp[nb].end();it++)
        {
            int vl=it->first+wg;
            int cnt=it->second+1;
            if(mp[i][k-vl])
                ans=min(ans,mp[i][k-vl]+cnt);
        }

        for(auto it=mp[nb].begin();it!=mp[nb].end();it++)
        {
            int vl=it->first+wg;
            int cnt=it->second+1;
            mp[i][vl]=min(mp[i][vl],cnt);
            if(mp[i][vl]==0)mp[i][vl]=cnt;
        }
    }
}


void calc(int i,int p)
{
    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)
{
    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)
{
    calc(i,n);
    int c=centroid(i,n);

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

int best_path(int N, int K, int H[][2], int L[])
{
    n=N;
    k=K;
    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]);
        v[H[i][0]].push_back(L[i]);
        v[H[i][1]].push_back(L[i]);
    }

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

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:15:18: 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:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'int centroid(int, int)':
race.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~
race.cpp: In function 'void solve(int)':
race.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~

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