Submission #1105989

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105989		underwaterkillerwhale	Team Coding (EGOI24_teamcoding)	C++17	100 / 100	979 ms	28752 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
const int Mod = 1e6 + 3;///lon
const ll INF = 1e18 + 7;
const ll BASE = 137;
const int szBL = 350;

int n, K;
int a[N];
vector<int> ke[N];
vector<int> setC[N], setH[N];///setC node màu C, setHi các node tại high i (lưu cái ein);
int ein[N], eout[N], high[N], numC[N], iniC[N], par[N], curR[N], maxH[N];///số C đã có sẵn trong root
bool covered[N];

void solution () {
    cin >> n >> K;
    rep (i, 1, n) {
        cin >> a[i];
        ++a[i];
        setC[a[i]].pb(i);
    }
    rep (i, 2, n) {
        cin >> par[i];
        ++par[i];
        ke[par[i]].pb(i);
    }
    function<void(int)> pdfs = [&] (int u) {
        static int time_dfs = 0;
        ein[u] = ++time_dfs;

        if (numC[a[u]]) covered[u] = 1;
        else curR[a[u]] = u;

        numC[a[u]]++;
        setH[high[u]].pb(ein[u]);
        iniC[curR[a[u]]]++;
        maxH[u] = high[u];
        iter (&v, ke[u]) {
            high[v] = high[u] + 1;
            pdfs (v);
            maxH[u] = max(maxH[u], maxH[v]);
        }
        eout[u] = time_dfs;
        --numC[a[u]];
    };
    pdfs(1);
    pii res = {-1, 0};
    auto get = [&] (int L, int R, int H) -> int {
        return (upper_bound(ALL(setH[H]), R) - setH[H].begin() - 1) - (lower_bound(ALL(setH[H]), L) - setH[H].begin() - 1);
    };
    auto process = [&] (int col) {
        vector<int> root, vecH;
        iter (&id, setC[col]) {
            if (!covered[id]) root.pb(id);
            numC[high[id]]++;
            vecH.pb(high[id]);
        }
        sort (ALL(vecH));
        vecH.resize(unique(ALL(vecH)) - vecH.begin());
        iter (&u, root) {
            int ansu = 0;
            iter (&H, vecH) {
                if (H > maxH[u]) break;
                if (H < high[u]) continue;
                ansu += min(numC[H], get(ein[u], eout[u], H));
            }
            res = max(res, {ansu, iniC[u]});
        }
        iter (&id, vecH) numC[id] = 0;
    };
    rep (i, 1, K) process(i);
    cout << res.fs <<" "<<res.fs - res.se <<"\n";
}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug challenge +12
*/

Compilation message (stderr)

Main.cpp:96:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   96 | main () {
      | ^~~~

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