Submission #480910

#	Time	Username	Problem	Language	Result	Execution time	Memory
480910		Mher	Race (IOI11_race)	C++14	100 / 100	1232 ms	61660 KiB

race

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cmath>
#include <bitset>
#include <unordered_map>
#include "race.h"

using namespace std;

const int n = 200003;

int s, k;
vector<pair<int, int>> g[n];
long long h[n];
int d[n];
bool mark[n];
int ans = -1;

void answer(int x)
{
    if (ans == -1)
        ans = x;
    else
        ans = min(ans, x);
}

void calc_height(int v, int p)
{
    d[v] = 1;
    for (pair<int, int> to : g[v])
    {
        if (to.first == p || mark[to.first])
            continue;

        h[to.first] = h[v] + to.second;
        calc_height(to.first, v);
        d[v] += d[to.first];
    }
}

int center(int v, int p, int sz)
{
    int t = -1;
    for (pair<int, int> to : g[v])
    {
        if (mark[to.first] || to.first == p)
            continue;

        if (d[to.first] > sz / 2)
        {
            t = to.first;
            break;
        }
    }
    return t == -1 ? v : center(t, v, sz);
}

void get_all(int v, int p, vector<pair<long long, int>>& st, long long dp, int l)
{
    st.push_back({ dp, l });
    for (auto to : g[v])
    {
        if (to.first == p || mark[to.first])
            continue;
        get_all(to.first, v, st, dp + to.second, l + 1);
    }
}

void solve(int v)
{
    //cout << v;
    calc_height(v, -1);
    v = center(v, -1, d[v]);
    mark[v] = true;
    calc_height(v, -1);
    map<long long, int> st;
    for (auto to : g[v])
    {
        if (mark[to.first])
            continue;
        vector<pair<long long, int>> dst;
        get_all(to.first, v, dst, to.second, 1);
        for (auto x : dst)
        {
            if (x.first > k)
                continue;
            if (x.first == k)
                answer(x.second);
            else if (st.count(k - x.first))
                answer(x.second + st[k - x.first]);
        }
        for (auto x : dst)
        {
            st[x.first] = st[x.first] != 0 ? min(x.second, st[x.first]) : x.second;
        }
        solve(to.first);
    }
}

int best_path(int N, int K, int H[][2], int L[])
{
    s = N;
    k = K;
    for (int i = 0; i < s - 1; i++)
    {
        int a, b, l;
        a = H[i][0];
        b = H[i][1];
        l = L[i];
        g[a].push_back({ b, l });
        g[b].push_back({ a, l });
    }
    solve(0);
    return ans;
}

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