Submission #1238726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238726		Jer	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	4096 ms	72464 KiB

Main

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

const int MAXN = 1e5 + 5;

int n, k;
int lang[MAXN];
vector<int> con[MAXN];
int dep[MAXN];

int timer = 0;
int tin[MAXN], tout[MAXN];

map<int, map<int, int>> depth_lang_count;

void dfs(int v, int d)
{
    tin[v] = timer++;
    dep[v] = d;
    depth_lang_count[d][lang[v]]++;
    for (int u : con[v])
        dfs(u, d + 1);
    tout[v] = timer;
}

bool is_subtree(int v, int u)
{
    return tin[v] <= tin[u] and tout[u] <= tout[v];
}

void collect_subtree(int v, int l, map<int, int> &wrong_at_depth, int &correct)
{
    if (lang[v] == l)
        correct++;
    else
        wrong_at_depth[dep[v]]++;

    for (int u : con[v])
        collect_subtree(u, l, wrong_at_depth, correct);
}

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++)
        scanf("%d", &lang[i]);

    for (int i = 1; i < n; i++)
    {
        int p;
        scanf("%d", &p);
        con[p].push_back(i);
    }

    dfs(0, 0);

    pair<int, int> best = {-1, -1};

    for (int team_lead = 0; team_lead < n; team_lead++)
    {
        int target_lang = lang[team_lead];
        map<int, int> wrong_in_subtree;
        int correct_in_subtree = 0;

        collect_subtree(team_lead, target_lang, wrong_in_subtree, correct_in_subtree);

        int swaps = 0;
        for (auto i : wrong_in_subtree)
        {
            int d = i.first, cnt = i.second;
            int total_good = depth_lang_count[d][target_lang];

            int in_subtree_good = 0;
            for (int i = 0; i < n; i++)
            {
                if (dep[i] == d and lang[i] == target_lang and is_subtree(team_lead, i))
                    in_subtree_good++;
            }

            int available_outside = total_good - in_subtree_good;
            swaps += min(cnt, available_outside);
        }

        int total = correct_in_subtree + swaps;
        pair<int, int> res = {total, swaps};

        if (res > best)
            best = res;
    }

    printf("%d %d\n", best.first, best.second);
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d%d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%d", &lang[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         scanf("%d", &p);
      |         ~~~~~^~~~~~~~~~

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