Submission #1195072

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195072		badge881	Team Coding (EGOI24_teamcoding)	C++20	42 / 100	4122 ms	843664 KiB

Main

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

vector<vector<ll>> edges;
vector<ll> pref;

ll n, k, timer = 0, tin[100005], tout[100005], depth[100005];
unordered_map<ll, ll> stuff[100005];
vector<ll> depths[100005], consider, prefs[100005];

ll ans = -1, ans2 = 0;
void dfs(ll a, ll d)
{
    depths[d].push_back(a);
    depth[a] = d;
    stuff[d][pref[a]] += 1;
    tin[a] = timer;
    timer += 1;
    for (auto &i : edges[a])
        dfs(i, d + 1);
    tout[a] = timer;
}

ll numchild(ll a, ll k)
{

    if (!(0 <= k && k < 100005))
        return 0;
    vector<ll> &sus = depths[k];
    if (sus.size() == 0)
        return 0;
    if (depth[a] == k)
        return 0;

    ll lo = 0;
    ll hi = sus.size() - 1;
    while (lo < hi)
    {
        ll mid = (lo + hi) / 2;
        if (tin[sus[mid]] >= tin[a])
            hi = mid;
        else
            lo = mid + 1;
    }
    ll leftp = lo;
    lo = 0;
    hi = sus.size() - 1;
    while (lo < hi)
    {
        ll mid = (lo + hi + 1) / 2;
        if (tout[sus[mid]] <= tout[a])
            lo = mid;
        else
            hi = mid - 1;
    }
    ll rightp = lo;

    if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a]))
        return 0;

    return max((ll)0, rightp - leftp + 1);
}

ll numspecialchild(ll a, ll k, ll c)
{

    if (!(0 <= k && k < 100005))
        return 0;
    vector<ll> &sus = depths[k];
    if (sus.size() == 0)
        return 0;
    if (depth[a] == k)
        return 0;

    ll lo = 0;
    ll hi = sus.size() - 1;
    while (lo < hi)
    {
        ll mid = (lo + hi) / 2;
        if (tin[sus[mid]] >= tin[a])
            hi = mid;
        else
            lo = mid + 1;
    }
    ll leftp = lo;
    lo = 0;
    hi = sus.size() - 1;
    while (lo < hi)
    {
        ll mid = (lo + hi + 1) / 2;
        if (tout[sus[mid]] <= tout[a])
            lo = mid;
        else
            hi = mid - 1;
    }
    ll rightp = lo;
    ll ans = 0;

    if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a]))
        return 0;
    for (ll i = leftp; i < rightp + 1; i++)
    {
        ans += (pref[sus[i]] == c);
    }

    return ans;
}

void solve(ll a)
{
    ll tans = 1;
    ll tans2 = 0;
    for (auto &i : consider)
    {
        ll temp = numchild(a, i);
        if (temp == 0)
            continue;
        tans += min(temp, stuff[i][pref[a]]);
        tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]);
    }

    if (tans > ans)
        ans = tans, ans2 = tans2;
    else if (tans == ans)
        ans2 = min(ans2, tans2);
}
void solve2(ll a)
{

    ll tans = 1;
    ll tans2 = 0;

    for (ll i = depth[a] + 1; i < n; i++)
    {
        ll temp = numchild(a, i);
        if (temp == 0)
            break;
        tans += min(temp, stuff[i][pref[a]]);
        tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]);
    }

    if (tans > ans)
        ans = tans, ans2 = tans2;
    else if (tans == ans)
        ans2 = min(ans2, tans2);
}

void dfs2(ll a, ll p)
{

    if (pref[a] == p)
    {
        solve2(a);
        return;
    }

    for (auto &i : edges[a])
        dfs2(i, p);
}

int main()
{

    for (ll i = 0; i < 100005; i++)
    {
        stuff[i].reserve(1 << 10);
        stuff[i].max_load_factor(0.25);
    }

    scanf("%lld %lld", &n, &k);

    for (ll i = 0; i < n; i++)
        edges.push_back({}), pref.push_back(0);

    for (ll i = 0; i < n; i++)
    {
        scanf("%lld", &pref[i]);
        prefs[pref[i]].push_back(i);
    }
    for (ll i = 1; i < n; i++)
    {
        ll temp;
        scanf("%lld", &temp);
        edges[temp].push_back(i);
    }
    dfs(0, 0);

    for (ll p = 0; p < k; p++)
    {

        if (prefs[p].size() > 400)
            dfs2(0, p);
        else
        {
            consider.clear();
            unordered_set<ll> temps;
            temps.reserve(1 << 18);
            temps.max_load_factor(0.25);
            for (auto &i : prefs[p])
                temps.insert(depth[i]);
            for (auto &i : temps)
                consider.push_back(i);

            for (auto &i : prefs[p])
                solve(i);
        }
    }

    printf("%lld %lld\n", ans, ans2);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |     scanf("%lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:178:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  178 |         scanf("%lld", &pref[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:184:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  184 |         scanf("%lld", &temp);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 19 / 19
• Subtask 3: 0 / 27
• Subtask 4: 23 / 23
• Subtask 5: 0 / 19