Submission #1210248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210248		cxijsijsjsyk	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	8 ms	12872 KiB

Main

#pragma optimize "Ofast"
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<unordered_map>
#include<cmath>
#include<cassert>
using namespace std;
vector<int> edges[100005];
pair<int, int> times[100005];
int depth[100005];
int col[100005]; int cnt = 1;
vector<int> depthtimes[100005];
vector<int> nwcol[100005];
unordered_map<int, int> dwcol[100005];
unordered_map<int, pair<int, int>> stdepth;// unordered_map<int, int> cldepth;
int bestans = 0; int bestswap = 1e9;
long long sum = 0;
void dfs(int n, int d) {
    times[n].first = cnt++;
    depth[n] = d;
    for (auto c : edges[n]) {
        dfs(c, d+1);
    }
    times[n].second = cnt++;
}

void find(int n, int cl, bool found) {
   // sum++;
    if (found) {
        stdepth[depth[n]].first++;
        if (col[n] == cl) stdepth[depth[n]].second++;
    }
    for (auto c : edges[n]) {
       if (col[n] == cl) find(c, cl, true);
       else find(c, cl, found);
    }
    if (col[n] == cl && !found) { // highest node with cl
        int curans = 0; int curswap = 0;
        for (auto& p : stdepth) {
            int t = dwcol[cl][p.first];
            curans += min(p.second.first, t);
            curswap += max(0, min(p.second.first, t)-p.second.second);
        }
        if (bestans == curans+1) {
            bestswap = min(bestswap, curswap);
        }
        else if (bestans < curans+1) {
            bestans = curans+1;
            bestswap = curswap;
        }
        stdepth.clear();
    }
}
int main() {
    int n, k; cin>>n>>k;
    for (int i = 0; i < n; i++) {
        cin>>col[i];
    }
    for (int i = 1; i < n; i++) {
        int x; cin>>x;
        edges[x].push_back(i);
    }
    
    dfs(0, 0);

    for (int i = 0; i < n; i++) {
        dwcol[col[i]][depth[i]]++;
    }

    for (int i = 0; i < n; i++) {
        depthtimes[depth[i]].push_back(times[i].first);
    }
    for (int i = 0; i <= n; i++) {
        sort(depthtimes[i].begin(), depthtimes[i].end());
    }
    for (int i = 0; i < n; i++) {
        nwcol[col[i]].push_back(i);
    }
    int sq = sqrt(n);
    // overall, sum of all cnt^2 = n
    for (int clr = 0; clr < k; clr++) {
        if (nwcol[clr].size() >= sq) {
           find(0, clr, false); // n algo, with log
        }
        else {
            cout<<"big"<<endl;
            continue;
            for (auto i : nwcol[clr]) { // cnt^2 with 
                map<int, int> used;
                map<int, int> swapped;
                int curans = 0;
                int curswap = 0;
                for (auto j : nwcol[clr]) {
                    if (j == i || depth[j] <= depth[i]) continue;
                    int up = upper_bound(depthtimes[depth[j]].begin(), depthtimes[depth[j]].end(), times[i].second)-depthtimes[depth[j]].begin();
                    int low = lower_bound(depthtimes[depth[j]].begin(), depthtimes[depth[j]].end(), times[i].first)-depthtimes[depth[j]].begin();
                    if (up-low-used[depth[j]]>0) {
                        used[depth[j]]++;
                        curans++;
                        swapped[depth[j]]++;
                        curswap++;
                    }
                    if (times[i].first < times[j].first && times[j].second < times[i].second) {
                        if (swapped[depth[j]]>0) {
                            swapped[depth[j]]--;
                            curswap--;  
                        }
                    }
                }
                if (bestans == curans+1) {
                    bestswap = min(bestswap, curswap);
                }
                else if (bestans < curans+1) {
                    bestans = curans+1;
                    bestswap = curswap;
                }
            }
        }
    }
   // cout<<sum<<endl;
    cout<<bestans<<" "<<bestswap<<endl;
} 

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