Submission #200063

#	Time	Username	Problem	Language	Result	Execution time	Memory
200063		SamAnd	Tax Evasion (LMIO19_mokesciai)	C++17	100 / 100	283 ms	55020 KiB

mokesciai

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;

int n, m;
vector<int> a[N];
bool c[N];

int d[N];
int q[N];

vector<int> v;
void dfs(int x)
{
    if (v.empty())
        d[x] = 1;
    else
        d[x] = d[v.back()] + 1;
    v.push_back(x);
    if (c[x])
    {
        int u = (v.size() / 2) - 1;
        ++q[v[v.size() - u - 1]];
    }
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        dfs(h);
    }
    v.pop_back();
}

struct ban
{
    int x, d;
    ban(){}
    ban(int x, int d)
    {
        this->x = x;
        this->d = d;
    }
};
bool operator<(const ban& a, const ban& b)
{
    return a.d < b.d;
}

priority_queue<ban> u[N];

void dfs1(int x)
{
    u[x].push(ban(x, d[x]));
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        dfs1(h);
        if (u[x].size() < u[h].size())
            swap(u[x], u[h]);
        while (!u[h].empty())
        {
            u[x].push(u[h].top());
            u[h].pop();
        }
    }
    for (int i = 0; i < q[x]; ++i)
    {
        c[u[x].top().x] = true;
        u[x].pop();
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 2; i <= n; ++i)
    {
        int p;
        scanf("%d", &p);
        a[p].push_back(i);
    }
    for (int i = 0; i < m; ++i)
    {
        int x;
        scanf("%d", &x);
        c[x] = true;
    }
    if (c[1])
    {
        printf("1\n");
        return 0;
    }
    dfs(1);
    memset(c, false, sizeof c);
    dfs1(1);
    int ans = N;
    for (int i = 1; i <= n; ++i)
    {
        if (c[i])
            ans = min(ans, d[i]);
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message (stderr)

mokesciai.cpp: In function 'void dfs(int)':
mokesciai.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
mokesciai.cpp: In function 'void dfs1(int)':
mokesciai.cpp:53:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
mokesciai.cpp: In function 'int main()':
mokesciai.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
mokesciai.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p);
         ~~~~~^~~~~~~~~~
mokesciai.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 39 / 39
• Subtask 4: 29 / 29