Submission #951817

#	Time	Username	Problem	Language	Result	Execution time	Memory
951817		codefox	Race (IOI11_race)	C++14	0 / 100	1 ms	2392 KiB

race

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

using namespace std;

#define ll long long
#define pii pair<int, int>
#define pli pair<ll, int>
#define f first
#define s second

int sol = 1e9;

void dfs(vector<vector<pii>> &graph, vector<int> &sub, int i, int p)
{
    sub[i]=1;
    for (pii ele:graph[i]) 
    {
        if (ele.f == p) continue;
        dfs(graph, sub, ele.f, i);
        sub[i] += sub[ele.f];
    }
}

int centroid(vector<vector<pii>> &graph, vector<int> &sub, int i, int p, int n)
{
    for (pii ele:graph[i])
    {
        if (ele.f == p) continue;
        if (sub[ele.f]*2 > n) return centroid (graph, sub, ele.f, i, n);
    }
    return i;
}

void finde(vector<vector<pii>> &graph, vector<pli> &dist, vector<int> &nodes, int i, int p, ll d, int di)
{
    di++;
    dist.push_back({d, di});
    nodes.push_back(i);
    for (pii ele:graph[i])
    {
        if (ele.f == p) continue;
        finde(graph, dist, nodes, ele.f, i, d+ele.s, di);
    }
}

void cd(vector<vector<pii>> &graph, int K)
{
    int n = graph.size();
    vector<int> sub(n, 0);

    dfs(graph, sub, 0, -1);
    int c = centroid(graph, sub, 0, -1, n);

    map<ll, int> paths;
    paths[0] = 0;

    vector<int> nind(n, 0);

    for (pii ele:graph[c])
    {
        vector<pli> dist;
        vector<int> nodes;
        finde(graph, dist, nodes, ele.f, c, ele.s, 0);
        for (pli d:dist)
        {
            if (d.f > K) continue;
            if (d.f == K) sol = min(sol, d.s);
            if (paths[K-d.f]==0) continue;
            sol = min(paths[K-d.f]+d.s, sol);
        }
        for (pli d:dist)
        {
            if (paths[d.f]==0) paths[d.f] = d.s;
            else paths[d.f] = min(paths[d.f], d.s);
        }
        for (int i = 0; i < nodes.size(); i++) nind[nodes[i]] = i;
        vector<vector<pii>> graph2(nodes.size());
        for (int node:nodes)
        {
            for (pii conn:graph[node])
            {
                if (conn.f==c) continue;
                graph2[nind[node]].push_back({nind[conn.f], conn.s});
            }
        }
        cd(graph2, K);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    vector<vector<pii>> graph(N);
    for (int i =0; i < N-1; i++)
    {
        graph[H[i][0]].push_back({H[i][1], L[i]});
        graph[H[i][1]].push_back({H[i][0], L[i]});
    }
    cd(graph, K);
    return sol;
}

/*
int32_t main()
{
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);

    int n, k;
    cin >> n >> k;
    int h[n-1][2];
    int l[n-1];
    for (int i = 0; i < n-1; i++)
    {
        cin >> h[i][0] >> h[i][1] >> l[i];
    }
    cout << best_path(n, k, h, l);
    return 0;
}
*/

Compilation message (stderr)

race.cpp: In function 'void cd(std::vector<std::vector<std::pair<int, int> > >&, int)':
race.cpp:77:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (int i = 0; i < nodes.size(); i++) nind[nodes[i]] = i;
      |                         ~~^~~~~~~~~~~~~~

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