Submission #539388

#	Time	Username	Problem	Language	Result	Execution time	Memory
539388		noedit	Race (IOI11_race)	C++17	9 / 100	242 ms	23224 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;
typedef long long ll;

const int MAXN = 2e5;
const int MAXK = 1e6 + 1;
vector<pair<ll, ll> > g[MAXN];
vector<ll>* vec[MAXN];

ll sz[MAXN], big[MAXN];
//map<ll, ll> cnt[MAXK];
map<ll, map<ll, ll> > cnt;
ll dep[MAXN];
ll d[MAXN];
void sizes(ll v, ll p, ll depth = 0, ll dist = 0)
{
    dep[v] = depth;
    d[v] = dist;
    sz[v] = 1;
    ll b = -1, mx = 0;
    for (auto& [u, w]: g[v])
    {
        if (u != p)
        {
            sizes(u, v, depth + 1, dist + w);
            sz[v] += sz[u];
            if (sz[u] > mx)
            {
                mx = sz[u];
                b = u;
            }
        }
    }
    big[v] = b;
}

ll ans = 1e9, k, n;

void dfs(ll v, ll p, bool keep = 0)
{
    for (auto& [u, w] : g[v])
    {
        if (u != p && u != big[v])
        {
            dfs(u, v, 0);
        }
    }
    if (big[v] != -1)
    {
        dfs(big[v], v, 1);
        vec[v] = vec[big[v]];
    }
    else
    {
        vec[v] = new vector<ll>();
    }
    vec[v]->push_back(v);
    ll y = k + d[v];
    if (cnt.count(y) && cnt[y].size() > 0 && cnt[y].begin()->first - dep[v] < ans)
    {
        ans = cnt[y].begin()->first - dep[v];
    }
        cnt[d[v]][dep[v]]++;
    for (auto& [u, w] : g[v])
    {
        if (u != p && u != big[v])
        {
            for (auto& w : *vec[u])
            {
                ll x = k * 1ll + 2 * 1ll * d[v] - d[w];
                if (cnt.count(x) && cnt[x].size() > 0)
                {
                    ll cur = cnt[x].begin()->first + dep[w];
                    if (cur - 2 * 1ll * dep[v] < ans)
                    {
                        ans = cur - 2 * dep[v];
                    }
                }
                vec[v]->push_back(w);
            }
            for (auto& w : *vec[u])
                cnt[d[w]][dep[w]]++;
        }
    }
    if (!keep)
    {
        for (auto& u : *vec[v])
        {
            cnt[d[u]][dep[u]]--;
            if (!cnt[d[u]].count(dep[u]))
                cnt[d[u]].erase(dep[u]);
            if (cnt[d[u]].empty())
                cnt.erase(d[u]);
        }
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N, k = K;
    for (int i = 0; i < n - 1; i++)
    {
        int x = H[i][0], y = H[i][1], z = L[i];
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }
    sizes(0, 0);
    dfs(0, 0);
    return (ans == 1e9 ? -1 :ans);
}

/*
4 3
0 1 1
1 2 2
1 3 4
2

*/

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