Submission #1315487

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315487		mikolaj00	경주 (Race) (IOI11_race)	C++20	100 / 100	928 ms	47172 KiB

race

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<pair<ll, int>>> g; 
vector<bool> dead;
vector<int> subtree_size;
int ans = INT_MAX;

void compute_subtree_size(int u, int p)
{
    subtree_size[u] = 1;
    for (auto[w, v] : g[u])
    {
        if (v == p || dead[v])
            continue;
        
        compute_subtree_size(v, u);
        subtree_size[u] += subtree_size[v];
    }
}

int find_centroid(int u, int p, int comp)
{
    for (auto[w, v] : g[u])
    {
        if (v == p || dead[v])
            continue;

        if (subtree_size[v] > comp/2)
            return find_centroid(v, u, comp);
    }
    return u;
}

map<ll, int> mp;
vector<pair<ll, int>> vals;
void dfs(int u, int p, ll dist, int path)
{
    vals.push_back({dist, path});
    for (auto[w, v] : g[u])
    {
        if (v == p || dead[v])
            continue;

        dfs(v, u, dist+w, path+1);
    }
}

void decompose(int u, ll K)
{
    compute_subtree_size(u, -1);
    int centroid = find_centroid(u, -1, subtree_size[u]);
    
    mp[0] = 0;
    for (auto[w, v] : g[centroid])
    {
        if (dead[v])
            continue;

        dfs(v, centroid, w, 1);

        for (auto vals_i : vals)
            if (mp.count(K-vals_i.first))
                ans = min(ans, vals_i.second + mp[K-vals_i.first]);

        for (auto vals_i : vals)
        {
            if (!mp.count(vals_i.first))
                mp[vals_i.first] = vals_i.second;
            else
                mp[vals_i.first] = min(mp[vals_i.first], vals_i.second);
        }
        
        vals.clear();
    }

    mp.clear();

    dead[centroid] = true;

    for (auto[w, v] : g[centroid])
    {
        if (dead[v])
            continue;

        decompose(v, K);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    g = vector<vector<pair<ll, int>>>(N);
    dead = vector<bool>(N);
    subtree_size = vector<int>(N);

    for (int i = 0; i < N-1; i++)
    {
        g[H[i][0]].push_back({L[i], H[i][1]});
        g[H[i][1]].push_back({L[i], H[i][0]});
    }

    decompose(0, K);
    int ans1 = ans;
    g.clear();
    dead.clear();
    subtree_size.clear();
    ans = INT_MAX;
    return (ans1 != INT_MAX ? ans1 : -1);
}

// int main()
// {
//     int N = 11;
//     int K = 12;
//     int H[10][2] = {{0, 1}, {0, 2}, {2, 3}, {3, 4}, {4, 5}, {0, 6}, {6, 7}, {6, 8}, {8, 9}, {8, 10}};
//     int L[10] = {3, 4, 5, 4, 6, 3, 2, 5, 6, 7};

//     cout << best_path(N, K, H, L);
// }

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