Submission #1164316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164316		canhnam357	Race (IOI11_race)	C++20	21 / 100	3094 ms	8444 KiB

race

#include <bits/stdc++.h>
#include "race.h"
using namespace std;
vector<vector<pair<int, int>>> adj;
vector<int> sz, del;
int ans = INT_MAX;
int dfs_sz(int u, int p)
{
    sz[u] = 1;
    for (auto [v, w] : adj[u])
    {
        if (v != p && !del[v])
        {
            sz[u] += dfs_sz(v, u);
        }
    }
    return sz[u];
}
int centroid(int u, int p, int n)
{
    for (auto [v, w] : adj[u])
    {
        if (v != p && !del[v] && sz[v] > n / 2) return centroid(v, u, n);
    }
    return u;
}
int t = 1, f;
const int MAXK = 1e6 + 1;
int has[MAXK] = {}, len[MAXK] = {};
void dfs1(int u, int p, int d, int h)
{
    if (d > f) return;
    if (has[f - d] == t)
    {
        ans = min(ans, h + len[f - d]);
    }
    for (auto [v, w] : adj[u])
    {
        if (v != p && !del[v])
        {
            dfs1(v, u, d + w, h + 1);
        }
    }
}
void dfs2(int u, int p, int d, int h)
{
    if (d > f) return;
    if (has[d] == t)
    {
        len[d] = min(len[d], h);
    }
    else
    {
        has[d] = t;
        len[d] = h;
    }
    for (auto [v, w] : adj[u])
    {
        if (v != p && !del[v])
        {
            dfs2(v, u, d + w, h + 1);
        }
    }
}
void solve(int u)
{
    int n = dfs_sz(u, u);
    int c = centroid(u, u, c);
    del[c] = 1;
    t++;
    has[0] = t;
    len[0] = 0;
    for (auto [v, w] : adj[c])
    {
        if (del[v]) continue;
        dfs1(v, c, w, 1);
        dfs2(v, c, w, 1);
    }
    for (auto [v, w] : adj[c]) if (!del[v]) solve(v);
}
int best_path(int N, int K, int H[][2], int L[])
{
    f = K;
    adj.resize(N);
    sz.resize(N);
    del.resize(N);
    for (int i = 0; i < N - 1; i++)
    {
        adj[H[i][0]].emplace_back(H[i][1], L[i]);
        adj[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    solve(0);
    return ans == INT_MAX ? -1 : ans;
}
// int main()
// {
//     int N = 11;
//     int K = 12;
//     int H[][2] = {
//         {0, 1},
//         {0, 2},
//         {2, 3},
//         {3, 4},
//         {4, 5},
//         {0, 6},
//         {6, 7},
//         {6, 8},
//         {8, 9},
//         {8, 10}
//     };
//     int L[] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};
//     cout << best_path(N, K, H, L);
//     return 0;
// }

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