Submission #49759

#	Time	Username	Problem	Language	Result	Execution time	Memory
49759		gs13105	Race (IOI11_race)	C++17	100 / 100	1625 ms	39316 KiB

race

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
#include <iterator>

using namespace std;

const int MAXN = 200000;

struct edg
{
    int x, w;
};

vector<edg> arr[MAXN + 10];
bool chk[MAXN + 10];
int cnt[MAXN + 10];
int k;

int sz;
void f(int x, int p)
{
    cnt[x] = 1;
    for(edg &e : arr[x])
    {
        if(chk[e.x] || e.x == p)
            continue;

        f(e.x, x);
        cnt[x] += cnt[e.x];
    }
}

int g(int x, int p)
{
    bool u = 1;
    int sum = 1;
    for(edg &e : arr[x])
    {
        if(chk[e.x] || e.x == p)
            continue;

        int t = g(e.x, x);
        if(t != -1)
            return t;

        if(cnt[e.x] > sz / 2)
            u = 0;
        sum += cnt[e.x];
    }
    if(!u || sz - sum > sz / 2)
        return -1;

    return x;
}

map<int, int> mem;
vector<pair<int, int>> add;
void h(int x, int p, int w, int l)
{
    add.push_back({ w, l });
    for(edg &e : arr[x])
    {
        if(chk[e.x] || e.x == p)
            continue;

        if(w + e.w <= k)
            h(e.x, x, w + e.w, l + 1);
    }
}

int solve(int a)
{
    f(a, a);
    sz = cnt[a];

    int c = g(a, a);
    assert(c != -1);

    mem.clear();
    mem[0] = 0;
    int res = -1;
    for(edg &e : arr[c])
    {
        if(chk[e.x])
            continue;

        add.clear();
        h(e.x, c, e.w, 1);

        for(auto &e : add)
        {
            auto it = mem.find(k - e.first);
            if(it != mem.end())
            {
                int t = it->second + e.second;
                if(res == -1 || t < res)
                    res = t;
            }
        }
        for(auto &e : add)
        {
            auto it = mem.find(e.first);
            if(it != mem.end())
                it->second = min(it->second, e.second);
            else
                mem[e.first] = e.second;
        }
    }

    chk[c] = 1;
    for(edg &e : arr[c])
    {
        if(chk[e.x])
            continue;
        
        int t = solve(e.x);
        if(res == -1 || t != -1 && t < res)
            res = t;
    }
    return res;
}

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

    k = K;
    return solve(0);
}

Compilation message (stderr)

race.cpp: In function 'int solve(int)':
race.cpp:130:33: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         if(res == -1 || t != -1 && t < res)
                         ~~~~~~~~^~~~~~~~~~

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