Submission #1158341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158341		eudhsyf	Race (IOI11_race)	C++20	0 / 100	3 ms	5696 KiB

race

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

using namespace std;

#define fi first
#define pb push_back
#define eb emplace_back
#define se second
typedef long long ll;
using pii = pair<int, int>;

const int nmax = 2e5 + 5, inf = 1e9;
int n, k, h[nmax][2], l[nmax];
int vis[nmax], sz[nmax];
vector<pii> adj[nmax];
unordered_map<int, int> mpa, mp;
int size(int u, int p = -1)
{
    sz[u] = 1;
    for (auto [v, w] : adj[u])
    {
        if (v != p && !vis[v])
        {
            sz[u] += size(v, u);
        }
    }
    return sz[u];
}
int find(int u, int n, int p = -1)
{
    for (auto [v, w] : adj[u])
    {
        if (v != p && !vis[v] && sz[v] >= n / 2)
        {
            return find(v, n, u);
        }
    }
    return u;
}
void cal(int u, int depth, int k, int cnt, int p = -1)
{
    if (depth > k)
    {
        return;
    }
    if (mp.count(depth) == 0)
        mp[depth] = cnt;
    else
        mp[depth] = min(mp[depth], cnt);
    for (auto [v, w] : adj[u])
    {
        if (vis[v] || v == p)
        {
            continue;
        }
        cal(v, depth + w, k, cnt + 1, u);
    }
}
int ans = inf;
void dfs_cal(int u, int k)
{
    int cent = find(u, size(u));
    if (vis[cent])
        return;
    vis[cent] = true;
    mpa[0] = 0;
    for (auto [v, w] : adj[cent])
    {
        if (vis[v])
            continue;
        cal(v, w, k, 1);
        for (auto x : mp)
        {
            if (k - x.fi < 0 || mpa.count(k - x.fi) == 0)
                continue;
            ans = min(ans, x.se + mpa[k - x.fi]);
        }
        for (auto x : mp)
        {
            if (mpa.count(x.fi) == 0)
                mpa[x.fi] = x.se;
            else
                mpa[x.fi] = min(mpa[x.fi], x.se);
        }
        mp.clear();
    }
    mpa.clear();
    for (auto [v, w] : adj[cent])
    {
        if (!vis[v])
        {
            dfs_cal(v, k);
        }
    }
}
int best_path(int n, int k, int h[][2], int l[])
{
    memset(vis, 0, sizeof(vis));
    for (int i = 1; i < n; i++) {
        h[i][0] ++, h[i][1] ++;
        adj[h[i][0]].emplace_back(h[i][1], l[i]);
        adj[h[i][1]].emplace_back(h[i][0], l[i]);
    }
    dfs_cal(1, k);
    if (ans == inf)
        return -1;
    return ans;
}

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