Submission #1080461

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080461		baluteshih	Team Coding (EGOI24_teamcoding)	C++14	100 / 100	287 ms	29512 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())
#ifdef bbq
#include <experimental/iterator>
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
void debug_(auto s, auto ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int f = 0;
    (..., (cerr << (f++ ? ", " : "") << a));
    cerr << ")\e[0m\n";
}
void orange_(auto s, auto L, auto R) {
    cerr << "\e[1;33m[" << s << "] = [";
    using namespace experimental;
    copy(L, R, make_ostream_joiner(cerr, ", "));
    cerr << "]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) safe
#define orange(...) safe
#endif

const int K = 320;
const int MAXN = 100005;

vector<int> G[MAXN], stk, dep, in, out;
int dft;

void dfs(int u, int d) {
    dep[u] = d, in[u] = ++dft;
    stk.pb(u + 1);
    for (int i : G[u])
        dfs(i, d + 1);
    stk.pb(-u - 1);
    out[u] = dft;
}

bool ancestor(int u, int v) {
    return in[u] <= in[v] && out[u] >= out[v];
}

pii operator+(const pii &a, const pii &b) {
    return pii(a.X + b.X, a.Y + b.Y);
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> arr(n), pa(n, -1);
    vector<vector<int>> buk(k), layer(k);
    dep.resize(n), in.resize(n), out.resize(n);
    for (int i = 0; i < n; ++i)
        cin >> arr[i], buk[arr[i]].pb(i);
    for (int i = 1; i < n; ++i) {
        cin >> pa[i];
        G[pa[i]].pb(i);
    }
    dfs(0, 0);

    pii ans = pii(0, 0);

    auto proc = [&](pii &cur, int f, int l, int a) {
        debug(f, l, a);
        assert(f >= a && l >= a);
        cur.X += min(f, l);
        cur.Y -= min(f, l) - a;
    };

    auto up = [&](auto &len, int i) {
        if (pa[i] != -1) {
            if (SZ(len[pa[i]]) < SZ(len[i]))
                len[pa[i]].swap(len[i]);
            for (int j = 0; j < SZ(len[i]); ++j)
                len[pa[i]][SZ(len[pa[i]]) - j - 1] = len[i][SZ(len[i]) - j - 1] + len[pa[i]][SZ(len[pa[i]]) - j - 1];
        }
    };

    auto solve_big = [&](int c) {
        vector<vector<pii>> len(n);
        vector<int> f(n);
        for (int i : buk[c])
            ++f[dep[i]];
        int vis = 0;
        for (int i : stk) {
            int flag = (arr[abs(i) - 1] == c);
            if (i > 0) vis += flag;
            else {
                i = -i - 1, vis -= flag;
                len[i].pb(pii(1, flag));
                if (flag) {
                    if (vis == 0) {
                        pii cur = pii(0, 0);
                        for (int j = 0; j < SZ(len[i]); ++j) {
                            int realf = f[dep[i] + j];
                            auto [reall, reala] = len[i][SZ(len[i]) - j - 1];
                            proc(cur, realf, reall, reala);
                        }
                        ans = max(ans, cur);
                    }
                }
                up(len, i);
            }
        }
    };

    vector<int> small, vis(n, -1), cnt(n), ina(n);
    auto solve_small = [&]() {
        vector<vector<int>> len(n);
        for (int c : small) {
            for (int i : buk[c]) {
                if (vis[dep[i]] != c) {
                    vis[dep[i]] = c;
                    layer[c].pb(dep[i]);
                }
            }
            sort(ALL(layer[c]));
        }
        for (int i : stk) {
            if (i > 0) continue;
            i = -i - 1;
            len[i].pb(1);
            debug("exit", i);
            orange(ALL(len[i]));
            if (SZ(buk[arr[i]]) < K) {
                pii cur = pii(0, 0);
                for (int j : layer[arr[i]])
                    cnt[j] = ina[j] = 0;
                for (int j : buk[arr[i]]) {
                    ++cnt[dep[j]];
                    if (ancestor(i, j))
                        ++ina[dep[j]];
                }
                for (int j : layer[arr[i]])
                    if (j >= dep[i]) {
                        if (SZ(len[i]) - 1 >= j - dep[i])
                            proc(cur, cnt[j], len[i][SZ(len[i]) - (j - dep[i]) - 1], ina[j]);
                    }
                ans = max(ans, cur);
            }
            up(len, i);
            if (i != 0) {
                debug("done up", i);
                orange(ALL(len[pa[i]]));
            }
        }
    };

    for (int i = 0; i < k; ++i) {
        if (SZ(buk[i]) >= K) solve_big(i);
        else small.pb(i);
    }
    solve_small();
    cout << ans.X << " " << -ans.Y << "\n";
}

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:107:34: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  107 |                             auto [reall, reala] = len[i][SZ(len[i]) - j - 1];
      |                                  ^

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