Submission #587600

#	Time	Username	Problem	Language	Result	Execution time	Memory
587600		Bobonbush	Race (IOI11_race)	C++17	0 / 100	992 ms	262144 KiB

race

#include <bits/stdc++.h>
#include"race.h"
#define foreach for
#define in :
using namespace std;
typedef long long ll;

/*
Konichiwa
Konichiwa
Ara ~~ ara

Bob no taisuki - Shinobu Kocho
    * * * * *
  *          *
 *         *
*         *        I love SHINOBU <3 <3 <3
 *         *
  *          *
    * * * * *
*/

/*
_________________________


    Author : Bob15324

_________________________
*/

template<class X , class Y>
    bool Minimize(X & x , Y y)
    {
        if( x == -1 || x >y )
        {
            x = y;
            return true;
        }
        return false;
    }

template<class X , class Y>
    bool Maximize(X & x , Y y)
    {
        if( x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

/* End of templates. Let's see what do we have here */
const int N = 2e5+1;
int res = -1;
class GRAPH
{
    private:
        vector<vector<pair<int ,int >>>vertices;
        vector<int>sub_size;
        vector<bool>dead;
    public:
        GRAPH(int _n)
        {
            vertices.resize(_n+1);
            sub_size.resize(_n+1);
            dead.resize(_n+1);
        }

        void AddEdge(int u ,int v ,int w)
        {
            vertices[u].push_back(make_pair(v , w));
            vertices[v].push_back(make_pair(u , w));
        }

        int DFS(int u ,int daddy)
        {
            sub_size[u] = 1;
            foreach(pair<int ,int > adj in vertices[u])
            {
                int v = adj.first;
                if(v == daddy)
                {
                    continue;
                }
                sub_size[u] += DFS(v , u);
            }
            return  sub_size[u];
        }

        int centroid(int u ,int daddy , int lim)
        {
            foreach(pair<int ,int > adj in vertices[u])
            {
                int v = adj.first;
                if(v == daddy)
                {
                    continue;
                }
                if(sub_size[v] > lim)
                {
                    return centroid(v , u , lim);
                }
            }
            return u;
        }

        void dfs2(int u ,int daddy ,int base  , int distance , map<int ,int > &cur , int s  ,int k )
        {
            if(cur.count(s))
            {
                Minimize(cur[s] , distance);
                
            }else
            {
                //cout << distance <<'\n';
                cur[s] = distance;
            }
            foreach(pair<int ,int > adj in vertices[u])
            {
                int v = adj.first;
                if(v == daddy || dead[v])
                {
                    continue;
                }
                if(s + adj.second > k)
                {
                    continue;
                }
                dfs2(v , u , base , distance + 1 ,cur ,  s + adj.second  , k);
            }
        }

        void Build(int u, int daddy ,int k )
        {
            int lim = DFS(u , daddy);
            int _c = centroid(u , daddy , lim >> 1);

            dead[_c] = true;

            map<int ,int >dict;
            foreach(pair<int ,int > adj in vertices[_c])
            {
                
                int v = adj.first;
                if(dead[v])
                {
                    continue;
                }
                
                map<int ,int >cur;
                dfs2(v , _c ,_c, 1 ,cur ,  adj.second , k );
                foreach(auto val in cur)
                {
                    if(dict.count(k - val.first))
                    {
                        
                        Minimize(res  , dict[k - val.first] + val.second);
                        
                    }
                }

                foreach(auto val in cur)
                {
                    if(dict.count(val.first))
                    {
                        Minimize(dict[val.first] , val.second);
                    }else
                    {
                        dict[val.first] = val.second;
                    }
                }
            }
            if(dict.count(k))
            {
                foreach(auto val in dict)
                {
                    if(val.first == k)
                        Minimize(res , val.second);
                }
            }
            dict.clear();

            foreach(pair<int ,int >adj in vertices[_c])
            {
                int v = adj.first;
                if(dead[v])
                {
                    continue;
                }
                Build(v , _c , k );
            }
        }
};


int best_path(int n , int m ,int H[][2] , int L[])
{
    GRAPH graph(n);
    for(int i = 0 ; i < n -1 ; i++)
    {
        H[i][0]++;
        H[i][1]++;
        graph.AddEdge(H[i][0] , H[i][1] , L[i]);
    }
    graph.Build(1 , - 1 , m);
    return res;
}


//Ehem. My code is amazing. Pay me 2$.Thank you.

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