Submission #1286664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286664		joylintp	경주 (Race) (IOI11_race)	C++20	21 / 100	3096 ms	18408 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define MP make_pair

int K, ans;
vector<vector<pair<int, int>>> edge;

vector<pair<int, int>> dfs(int u, int par)
{
    multiset<pair<int, int>> ms;
    vector<vector<pair<int, int>>> rets;
    for (auto &[v, w] : edge[u])
        if (v != par)
        {
            vector<pair<int, int>> ret = dfs(v, u);
            for (auto &p : ret)
            {
                p.F += w, p.S++;
                ms.insert(p);
                if (p.F == K)
                    ans = min(ans, p.S);
            }
            rets.push_back(ret);
        }
    for (auto &v : rets)
    {
        for (auto &p : v)
            ms.erase(ms.find(p));
        for (auto &p : v)
        {
            auto it = ms.lower_bound(make_pair(K - p.first, 0));
            if (it != ms.end() && it -> first == K - p.first)
                ans = min(ans, p.second + it -> second);
        }
        for (auto &p : v)
            ms.insert(p);
    }

    vector<pair<int, int>> ret;
    ret.push_back(make_pair(0, 0));
    for (auto it = ms.begin(); it != ms.end(); )
    {
        ret.push_back(*it);
        auto jt = it;
        while (jt != ms.end() && it -> first == jt -> first)
            jt++;
        it = jt;
    }
    return ret;
}

int best_path(int N, int K_, int H[][2], int L[])
{
    K = K_;
    edge.resize(N);
    for (int i = 0; i + 1 < N; i++)
    {
        edge[H[i][0]].push_back(MP(H[i][1], L[i]));
        edge[H[i][1]].push_back(MP(H[i][0], L[i]));
    }
    ans = N, dfs(0, 0);
    return ans == N ? -1 : ans;
}

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