Submission #1140750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1140750		Aliyyiakbar	Race (IOI11_race)	C++20	100 / 100	1244 ms	41168 KiB

race

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

const int sz = 3e5 + 9;
vector< pair<int, int> > v[sz];
map<int, int> mp;
bool used[sz];

int ans = 1e9, k;

int centroidDecomp(int node, int par, int n, int &centroid)
{
    int res = 1;
    for (auto to : v[node])
    {
        if (!used[to.first] && to.first != par)
        {
            res += centroidDecomp(to.first, node, n, centroid);
        }
    }
    if (centroid == -1 && (par == -1 || ((res << 1) >= n)))
    {
        centroid = node;
    }
    return res;
}

void dfs(int node, int par, int dist, int depth, int typ)
{
    if (dist == k)
    {
        ans = min(ans, depth);
        return;
    }
    if (!typ)
    {
        if (mp.find(k - dist) != mp.end())
        {
            ans = min(ans, mp[k - dist] + depth);
        }
    }
    else
    {
        if (mp.find(dist) == mp.end())
        {
            mp[dist] = depth;
        }
        mp[dist] = min(mp[dist], depth);
    }
    for (auto to : v[node])
    {
        if (!used[to.first] && to.first != par)
        {
            dfs(to.first, node, dist + to.second, depth + 1, typ);
        }
    }
}

void calc(int l, int r)
{
    int centroid = -1;
    centroidDecomp(l, -1, r, centroid);
    used[centroid] = 1;
    mp.clear();
    for (auto x : v[centroid])
    {
        if (!used[x.first])
        {
            dfs(x.first, l, x.second, 1, 0);
            dfs(x.first, l, x.second, 1, 1);
        }
    }
    for (auto x : v[centroid])
    {
        if (!used[x.first])
        {
            calc(x.first, (r >> 1));
        }
    }
}

int best_path(int n, int K, int h[][2], int l[])
{
    for (int i = 0; i < n - 1; ++i)
    {
        v[h[i][0] + 1].emplace_back(h[i][1] + 1, l[i]);
        v[h[i][1] + 1].emplace_back(h[i][0] + 1, l[i]);
    }
    k = K;
    calc(1, n);
    return (ans == 1e9 ? -1 : ans);
}

/*
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3 4 5 4 6 3 2 5 6 7
2
*/

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