Submission #1099594

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

race

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

#define ternal asdasf


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

void DFS(long long u , long long 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];
        }
}

long long find_centroid(long long u , long long tree_sz , long long 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(long long u , long long par , long long h , long long len)
{
    if(ternal.find(h) == ternal.end())
        ternal[h] = len;
    else
        ternal[h] = min(ternal[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])
            solve(v.first , u  , h + v.second , len + 1);
}

void build_centroid(long long u)
{
    DFS(u , -1);
    long long 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: ternal)
            {
                if(global.find(x.first) == global.end())
                    global[x.first] = x.second;
                else
                    global[x.first] = min(global[x.first] , x.second);
            }
            ternal.clear();
        }
    global.clear();
    is_centroid[centroid] = true;
    for(auto v: g[centroid])
        if(!is_centroid[v.first])
            build_centroid(v.first);
}

long long best_path(int m , int p , int h[][2] , int l[])
{
    k = p;
    n = m;
    for(long long 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("centroid.INP","r",stdin);
////    freopen("BIEUTHUCNT.OUT","w",stdout);
//    ios::sync_with_stdio(0);
//    cin.tie(0);
//    cin >> n >> k;
//    for(long long i = 1 ; i <= n - 1 ; i++)
//    {
//        long long 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