Submission #95097

#	Time	Username	Problem	Language	Result	Execution time	Memory
95097		Alexa2001	Race (IOI11_race)	C++17	100 / 100	1202 ms	56740 KiB

race

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

using namespace std;

const int Nmax = 2e5 + 5, inf = 1e9;

int w[Nmax], best[10 * Nmax], All, K;
bool used[Nmax];

vector<int> v[Nmax], c[Nmax];



void dfs(int node, int dad = -1)
{
    w[node] = 1;
    for(auto it : v[node])
        if(!used[it] && it != dad)
        {
            dfs(it, node);
            w[node] += w[it];
        }
}

pair<int,int> centroid(int node, int dad = -1)
{
    int act = All - w[node];
    pair<int,int> ans = {All+1, All};

    for(auto it : v[node])
        if(!used[it] && it != dad)
        {
            ans = min(ans, centroid(it, node));
            act = max(act, w[it]);
        }
    ans = min(ans, {act, node});
    return ans;
}

void dfs2(int node, int dad, int up, int level, vector< pair<int,int> > &now)
{
    if(up <= K)
        now.push_back({up, level});

    int i, x, cost;
    for(i=0; i<v[node].size(); ++i)
    {
        x = v[node][i];
        cost = c[node][i];
        if(used[x] || x == dad) continue;

        dfs2(x, node, up + cost, level+1, now);
    }
}

int solve(int node)
{
    dfs(node);
    All = w[node];
    node = centroid(node).second;

    vector< pair<int,int> > now;
    vector<int> pos;
    int i, son, cost, ans = inf;

    best[0] = 0;

    for(i=0; i<v[node].size(); ++i)
    {
        son = v[node][i];
        cost = c[node][i];
        if(used[son]) continue;

        now.clear();
        dfs2(son, node, cost, 1, now);

        for(auto it : now)
            ans = min(ans, it.second + best[K - it.first]);

        for(auto it : now)
        {
            best[it.first] = min(best[it.first], it.second);
            pos.push_back(it.first);
        }
    }

    for(auto it : pos) best[it] = inf;

    used[node] = 1;

    for(auto it : v[node])
        if(!used[it])
            ans = min(ans, solve(it));
    return ans;
}

int best_path(int N, int _K, int H[][2], int L[])
{
    K = _K;
    int i;
    for(i=0; i<N-1; ++i)
    {
        int x, y, z;
        x = H[i][0];
        y = H[i][1];
        z = L[i];

        v[x].push_back(y);
        v[y].push_back(x);
        c[x].push_back(z);
        c[y].push_back(z);
    }

    for(i=0; i<=K; ++i) best[i] = inf;

    int X = solve(0);
    if(X == inf) return -1;
    return X;
}

Compilation message (stderr)

race.cpp: In function 'void dfs2(int, int, int, int, std::vector<std::pair<int, int> >&)':
race.cpp:47:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~
race.cpp: In function 'int solve(int)':
race.cpp:69:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0; i<v[node].size(); ++i)
              ~^~~~~~~~~~~~~~~

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