Submission #1094904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094904		raphaelp	Team Coding (EGOI24_teamcoding)	C++14	81 / 100	4048 ms	187236 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void dfs(int x, int p, vector<vector<int>> &sons, vector<int> &depth, int prof, vector<vector<int>> &lca)
{
    depth[x] = prof;
    lca[0][x] = p;
    for (int i = 0; i < sons[x].size(); i++)
    {
        dfs(sons[x][i], x, sons, depth, prof + 1, lca);
    }
}
void dfs2(int x, vector<vector<int>> &sons, vector<int> &Tab, vector<vector<pair<int, int>>> &colors, vector<vector<pair<int, int>>> &sub, vector<pair<int, int>> &ans, vector<int> &big, vector<map<int, int>> &M, map<int, int> &space, vector<int> &num, vector<int> &swaps, vector<vector<int>> &precalc, vector<vector<int>> &taken, int prof)
{
    map<int, int> space2;
    space2[prof]++;
    vector<int> num2(big.size()), swaps2(big.size());
    vector<map<int, int>> M2(big.size());
    if (colors[Tab[x]].size() > sqrt(sons.size()))
    {
        int temp = lower_bound(big.begin(), big.end(), Tab[x]) - big.begin();
        M2[temp][prof]++;
        num2[temp]++;
    }
    for (int i = 0; i < big.size(); i++)
    {
        swaps2[i] -= num2[i];
        num2[i] = min(precalc[i][prof], space2[prof]);
        swaps2[i] += num2[i];
    }
    for (int i = 0; i < sons[x].size(); i++)
    {
        dfs2(sons[x][i], sons, Tab, colors, sub, ans, big, M, space, num, swaps, precalc, taken, prof + 1);
        if (space.size() > space2.size())
        {
            swap(space, space2);
            swap(M, M2);
            swap(num, num2);
            swap(swaps, swaps2);
        }
        for (auto val : space)
        {
            for (int j = 0; j < big.size(); j++)
            {
                swaps2[j] -= min(space2[val.first], precalc[j][val.first]) - M2[j][val.first];
                num2[j] -= min(space2[val.first], precalc[j][val.first]);
                num2[j] += min(space2[val.first] + val.second, precalc[j][val.first]);
                swaps2[j] += min(space2[val.first] + val.second, precalc[j][val.first]) - M2[j][val.first] - M[j][val.first];
                if (M2[j][val.first] == 0)
                    M2[j].erase(val.first);
                if (M[j][val.first] == 0)
                    M[j].erase(val.first);
            }
            space2[val.first] += val.second;
        }
        for (int j = 0; j < big.size(); j++)
        {
            for (auto val : M[j])
            {
                M2[j][val.first] += val.second;
            }
        }
    }
    if (colors[Tab[x]].size() > sqrt(sons.size()))
    {
        int temp = lower_bound(big.begin(), big.end(), Tab[x]) - big.begin();
        ans[x] = {num2[temp], swaps2[temp]};
    }
    else
    {
        for (int i = 0; i < taken[x].size(); i++)
            space2[taken[x][i]]--;
        for (int i = 0; i < sub[x].size(); i++)
        {
            space2[sub[x][i].first]--;
            if (space2[sub[x][i].first] >= 0)
            {
                ans[x].first++;
                ans[x].second++;
            }
        }
        for (int i = 0; i < sub[x].size(); i++)
        {
            space2[sub[x][i].first]++;
            if (space2[sub[x][i].first] == 0)
                space2.erase(sub[x][i].first);
        }
        for (int i = 0; i < taken[x].size(); i++)
        {
            space2[taken[x][i]]++;
            if (space2[taken[x][i]] == 0)
                space2.erase(taken[x][i]);
        }
    }
    swap(M, M2);
    swap(space, space2);
    swap(num, num2);
    swap(swaps, swaps2);
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int N, K;
    cin >> N >> K;
    vector<int> Tab(N);
    vector<vector<pair<int, int>>> colors(K);
    for (int i = 0; i < N; i++)
    {
        cin >> Tab[i];
        colors[Tab[i]].push_back({0, i});
    }
    vector<int> big, small;
    for (int i = 0; i < K; i++)
        if (colors[i].size() > sqrt(N))
            big.push_back(i);
        else
            small.push_back(i);
    vector<vector<int>> sons(N);
    for (int i = 0; i < N - 1; i++)
    {
        int x;
        cin >> x;
        sons[x].push_back(i + 1);
    }
    vector<int> depth(N);
    vector<vector<int>> lca(log2(N) + 1, vector<int>(N));
    dfs(0, 0, sons, depth, 0, lca);
    for (int i = 1; i <= log2(N); i++)
    {
        for (int j = 0; j < N; j++)
        {
            lca[i][j] = lca[i - 1][lca[i - 1][j]];
        }
    }
    for (int i = 0; i < K; i++)
    {
        for (int j = 0; j < colors[i].size(); j++)
        {
            colors[i][j].first = depth[colors[i][j].second];
        }
        sort(colors[i].begin(), colors[i].end());
    }
    vector<vector<pair<int, int>>> sub(N);
    vector<vector<int>> taken(N);
    vector<pair<int, int>> ans(N);
    for (int i = 0; i < small.size(); i++)
    {
        int cur = small[i];
        for (int j = 0; j < colors[cur].size(); j++)
        {
            ans[colors[cur][j].second].first++;
            for (int k = 0; k < colors[cur].size(); k++)
            {
                if (colors[cur][k].first == colors[cur][j].first)
                    break;
                int a = colors[cur][j].second;
                for (int l = log2(N); l >= 0; l--)
                    if (depth[lca[l][a]] >= depth[colors[cur][k].second])
                        a = lca[l][a];
                if (a == colors[cur][k].second)
                {
                    ans[colors[cur][k].second].first++;
                    taken[colors[cur][k].second].push_back(colors[cur][j].first);
                    continue;
                }
                sub[colors[cur][k].second].push_back(colors[cur][j]);
            }
        }
    }
    vector<map<int, int>> M(big.size());
    map<int, int> space;
    vector<int> num(big.size()), swaps(big.size());
    vector<vector<int>> precalc(big.size(), vector<int>(N));
    for (int i = 0; i < big.size(); i++)
    {
        for (int j = 0; j < colors[big[i]].size(); j++)
        {
            precalc[i][colors[big[i]][j].first]++;
        }
    }
    dfs2(0, sons, Tab, colors, sub, ans, big, M, space, num, swaps, precalc, taken, 0);
    int best = 0, best2 = 0;
    for (int i = 0; i < N; i++)
    {
        if (ans[i].first > best || (ans[i].first == best && ans[i].second < best2))
        {
            best = ans[i].first;
            best2 = ans[i].second;
        }
    }
    cout << best << ' ' << best2;
}

Compilation message (stderr)

Main.cpp: In function 'void dfs(int, int, std::vector<std::vector<int> >&, std::vector<int>&, int, std::vector<std::vector<int> >&)':
Main.cpp:7:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i = 0; i < sons[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
Main.cpp: In function 'void dfs2(int, std::vector<std::vector<int> >&, std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<std::pair<int, int> >&, std::vector<int>&, std::vector<std::map<int, int> >&, std::map<int, int>&, std::vector<int>&, std::vector<int>&, std::vector<std::vector<int> >&, std::vector<std::vector<int> >&, int)':
Main.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < big.size(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for (int i = 0; i < sons[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
Main.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             for (int j = 0; j < big.size(); j++)
      |                             ~~^~~~~~~~~~~~
Main.cpp:55:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int j = 0; j < big.size(); j++)
      |                         ~~^~~~~~~~~~~~
Main.cpp:70:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int i = 0; i < taken[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int i = 0; i < sub[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i = 0; i < sub[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~
Main.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < taken[x].size(); i++)
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:138:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |         for (int j = 0; j < colors[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~
Main.cpp:147:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int i = 0; i < small.size(); i++)
      |                     ~~^~~~~~~~~~~~~~
Main.cpp:150:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  150 |         for (int j = 0; j < colors[cur].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:153:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for (int k = 0; k < colors[cur].size(); k++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~
Main.cpp:175:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |     for (int i = 0; i < big.size(); i++)
      |                     ~~^~~~~~~~~~~~
Main.cpp:177:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  177 |         for (int j = 0; j < colors[big[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~~

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