제출 #1020650

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1020650		vjudge1	Jobs (BOI24_jobs)	C++11	0 / 100	5 ms	8284 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const long long mx = (1LL << 31) - 1, maxn = 5 * 1e4 + 1;

vector<long long> a[maxn];

long long b[maxn];

bool visited[maxn];

set<long long> c[maxn];

long long res[maxn];

void dfs(long long u)
{
    visited[u] = true;

    res[u] = mx;

    for (int e : a[u])
    {
        if (!visited[e])
        {
            dfs(e);

            res[u] = min(res[u], res[e]);

            if (c[u].size() < c[e].size())
            {
                swap(c[u], c[e]);
            }

            for (auto it = c[e].begin(); it != c[e].end(); it ++)
            {
                auto p1 = c[u].lower_bound(*it);

                auto p2 = p1;

                if (p1 != c[u].begin())
                {
                    p1 --;

                    res[u] = min(res[u], abs(*it - *p1));
                }

                if (p2 != c[u].end())
                {
                    res[u] = min(res[u], abs(*it - *p2));
                }

                c[u].insert(*it);
            }
        }
    }
}

int main()
{
    long long n, m;

    cin >> n >> m;

    for (int i = 2; i <= n; i ++)
    {
        long long u;

        cin >> u;

        a[u].push_back(i);
    }

    for (int i = n - m + 1; i <= n; i ++)
    {
        cin >> b[i];

        c[i].insert(b[i]);
    }

    dfs(1);

    for (int i = 1; i <= n - m; i ++)
    {
        cout << res[i] << " ";
    }

}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31