Submission #348752

#	Time	Username	Problem	Language	Result	Execution time	Memory
348752		idk321	Race (IOI11_race)	C++11	43 / 100	526 ms	192492 KiB

race

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

using namespace std;
typedef long long ll;

const int N = 200001;
const int K = 101;

vector<array<int, 2>> adj[N];
int dp[N][K];
int anc[N][30];
ll danc[N][30];
int h[N];
//int par[N];
int n, k;

array<ll, 2> lca(int a, int b)
{
    if (h[a] < h[b]) swap(a, b);
    ll dist = 0;
    int edge = 0;
    for (int i = 29; i >= 0; i--)
    {
        if (h[a] - (1 << i) >= h[b])
        {
            edge += 1 << i;
            dist += danc[a][i];
            a = anc[a][i];
        }
    }

    if (a == b) return {edge, dist};

    for (int i = 29; i >= 0; i--)
    {
        if (anc[a][i] != anc[b][i])
        {
            edge += 2 * (1 << i);
            dist += danc[a][i];
            dist += danc[b][i];
            a = anc[a][i];
            b = anc[b][i];
        }
    }

    edge += 2;
    dist += danc[a][0];
    dist += danc[b][0];
    return {edge, dist};
}

void dfs2(int node, int parent, int pdist)
{
    if (parent == -1)
    {
        h[node] = 0;
        for (int i = 0; i < 30; i++) anc[node][i] = -1;
        for (int i = 0; i < 30; i++) danc[node][i] = -1;
    } else
    {
        h[node] = h[parent] + 1;
        anc[node][0] = parent;
        danc[node][0] = pdist;
        for (int i = 1; i < 30; i++)
        {
            if (anc[node][i - 1] == -1) anc[node][i] = -1;
            else
            {
                anc[node][i] = anc[anc[node][i - 1]][i - 1];
            }
        }
        for (int i = 1; i < 30; i++)
        {
            if (anc[node][i] == -1) danc[node][i] = -1;
            else
            {
                danc[node][i] = danc[node][i - 1] + danc[anc[node][i - 1]][i - 1];
            }
        }
    }

    for (auto next : adj[node])
    {
        if (next[0] == parent) continue;
        dfs2(next[0], node, next[1]);
    }
}

int dfs1(int node, int parent)
{
    dp[node][0] = 0;
    //par[node] = parent;
    int res = N;
    vector<int> bestAt(k + 1, N);
    bestAt[0] = 0;
    for (auto next : adj[node])
    {
        if (next[0] == parent) continue;

        res = min(res, dfs1(next[0], node));
        for (int i = 0; i + next[1] <= k; i++)
        {
            //cout << node << " " << next[0] << " " << i << " " << dp[next[0]][i] << endl;
            dp[node][i + next[1]] = min(dp[node][i + next[1]], dp[next[0]][i] + 1);
            res = min(res, dp[next[0]][i] + 1 + bestAt[k - i - next[1]]);
        }
        for (int i = 0; i + next[1] <= k; i++)
        {
            bestAt[i + next[1]] = min(bestAt[i + next[1]], dp[next[0]][i] + 1);
        }
    }

    return res;
}

int best_path(int n1, int k1, int H[][2], int L[])
{
    n = n1;
    k = k1;
    for (int i = 0; i < n; i++) for (int j = 0; j <= k; j++) dp[i][j] = N;
    for (int i = 0; i < n - 1; i++)
    {
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }

    int res = N;
    if (n > 1000)
    {
        res = dfs1(0, -1);
    } else
    {
        dfs2(0, -1, -1);
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                auto curr = lca(i, j);
                if (curr[1] == k) res = min<int>(curr[0], res);
            }
        }
    }
    if (res == N) return -1;
    return res;
}

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