Submission #1340164

#	Time	Username	Problem	Language	Result	Execution time	Memory
1340164		yogesh_sane	Team Coding (EGOI24_teamcoding)	C++20	Compilation error	0 ms	0 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
int lang[MAXN], depth[MAXN], tin[MAXN], tout[MAXN], timer;
vector<int> nodes_at_depth[MAXN];
vector<int> lang_at_depth[MAXN][10] ; // This is a simplification; use a more efficient structure for large K

// For large K, we store only existing depths for each language
map<int, vector<int>> lang_depths[MAXN]; 

void dfs(int u, int d) {
    depth[u] = d;
    tin[u] = ++timer;
    nodes_at_depth[d].push_back(tin[u]);
    lang_depths[lang[u]][d].push_back(tin[u]);
    for (int v : adj[u]) {
        dfs(v, d + 1);
    }
    tout[u] = timer;
}

// Counts nodes in subtree of u at a specific depth
int count_in_subtree(const vector<int>& vec, int u_tin, int u_tout) {
    return upper_bound(vec.begin(), vec.end(), u_tout) - lower_bound(vec.begin(), vec.end(), u_tin);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> lang[i];
    for (int i = 1; i < N; i++) {
        int p; cin >> p;
        adj[p].push_back(i);
    }

    dfs(0, 0);

    long long max_p = 0, min_s = 0;

    // Iterate over all possible leaders
    for (int u = 0; u < N; u++) {
        // We only care about languages that exist at depth[u]
        // In a full solution, you'd optimize this loop to not re-check languages
        for (auto const& [c, d_list] : lang_depths) {
            if (lang_depths[c].count(depth[u])) {
                long long current_p = 0;
                long long current_s = 0;
                
                // Calculate value for this leader u and language c
                for (auto const& [d, v_tins] : lang_depths[c]) {
                    if (d < depth[u]) continue;
                    int total_c_at_d = v_tins.size();
                    int space_in_subtree = count_in_subtree(nodes_at_depth[d], tin[u], tout[u]);
                    int initial_c_in_subtree = count_in_subtree(v_tins, tin[u], tout[u]);
                    
                    int target_c = min(total_c_at_d, space_in_subtree);
                    current_p += target_c;
                    current_s += max(0, target_c - initial_c_in_subtree);
                }

                if (current_p > max_p) {
                    max_p = current_p;
                    min_s = current_s;
                } else if (current_p == max_p) {
                    if (max_p > 0) min_s = min(min_s, current_s);
                }
            }
        }
    }

    cout << max_p << " " << min_s << endl;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:53:26: error: cannot decompose inaccessible member 'std::map<int, std::vector<int> >::_M_t' of 'const std::map<int, std::vector<int> >'
   53 |         for (auto const& [c, d_list] : lang_depths) {
      |                          ^~~~~~~~~~~
In file included from /usr/include/c++/13/map:63,
                 from Main.cpp:4:
/usr/include/c++/13/bits/stl_map.h:158:17: note: declared private here
  158 |       _Rep_type _M_t;
      |                 ^~~~