Submission #1099591

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099591		nhamtan	Race (IOI11_race)	C++17	0 / 100	3 ms	4956 KiB

race

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

#define internal asdasf


const int N = 2e5 + 5;
int n , k , ans = 1e9;
int sz[N];
bool is_centroid[N];
vector < pair < int , int > > g[N];
map < int , int > internal , global;

void DFS(int u , int par)
{
    sz[u] = 1;
    for(auto v: g[u])
        if(v.first != par && !is_centroid[v.first])
        {
            DFS(v.first , u);
            sz[u] += sz[v.first];
        }
}

int find_centroid(int u , int tree_sz , int par)
{
    for(auto v: g[u])
        if(v.first != par && !is_centroid[v.first] && sz[v.first] > tree_sz / 2)
            return find_centroid(v.first , tree_sz , u);
    return u;
}

void solve(int u , int par , int h , int len)
{
    if(internal.find(h) == internal.end())
        internal[h] = len;
    else
        internal[h] = min(internal[h] , len);

    if(global.find(k - h) != global.end())
        ans = min(ans , len + global[k - h]);

    for(auto v: g[u])
        if(v.first != par && !is_centroid[v.first] && (long long)h + v.second <= k)
            solve(v.first , u  , h + v.second , len + 1);
}

void build_centroid(int u)
{
    DFS(u , -1);
    int centroid = find_centroid(u , sz[u] , -1);
    global[0] = 0;
    for(auto v: g[centroid])
        if(!is_centroid[v.first])
        {
            solve(v.first , centroid , v.second , 1);
            for(auto x: internal)
            {
                if(global.find(x.first) == global.end())
                    global[x.first] = x.second;
                else
                    global[x.first] = min(global[x.first] , x.second);
            }
            internal.clear();
        }
    global.clear();
    is_centroid[centroid] = true;
    for(auto v: g[centroid])
        if(!is_centroid[v.first])
            build_centroid(v.first);
}

int best_path(int m , int p , int h[][2] , int l[])
{
    k = p;
    n = m;
    for(int i = 0 ; i <= n - 1 ; i++)
    {
        h[i][0]++;
        h[i][1]++;
        g[h[i][0]].push_back({h[i][1] , l[i]});
        g[h[i][1]].push_back({h[i][0] , l[i]});
    }
    build_centroid(1);
    if(ans == 1e9)
        return -1;
    else
        return ans;
}

//main()
//{
////    freopen("BIEUTHUCNT.INP","r",stdin);
////    freopen("BIEUTHUCNT.OUT","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cin >> n >> k;
//    for(int i = 1 ; i <= n - 1 ; i++)
//    {
//        int u , v , w;
//        cin >> u >> v >> w;
//        u++;v++;
//        g[u].push_back({v , w});
//        g[v].push_back({u , w});
//    }
//    build_centroid(1);
//    if(ans == 1e9)
//        cout << "-1";
//    else
//        cout << ans << "\n";
//}

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