oj.uz

Submission #1080433

# Submission time Handle Problem Language Result Execution time Memory
1080433 2024-08-29T09:55:01 Z baluteshih Team Coding (EGOI24_teamcoding) C++17
12 / 100
 66 ms 29564 KB 
#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][j] + 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);
            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]) {
                        proc(cur, cnt[j], len[i][SZ(len[i]) - (j - dep[i]) - 1], ina[j]);
                    }
                ans = max(ans, cur);
            }
            up(len, 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";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2812 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 48 ms 26568 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 28 ms 21652 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 2 ms 3164 KB Output is correct
15 Correct 66 ms 29564 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct

Subtask #2
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2904 KB Output is correct
2 Correct 1 ms 2624 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 3164 KB Output is correct
5 Correct 28 ms 21724 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 34 ms 13552 KB Output is correct
9 Correct 2 ms 2652 KB Output is correct
10 Runtime error 4 ms 5724 KB Execution killed with signal 6
11 Halted 0 ms 0 KB -

Subtask #3
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 2 ms 2588 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 61 ms 26412 KB Output is correct
9 Correct 2 ms 2648 KB Output is correct
10 Correct 4 ms 3328 KB Output is correct
11 Correct 53 ms 29452 KB Output is correct
12 Runtime error 3 ms 5212 KB Execution killed with signal 6
13 Halted 0 ms 0 KB -

Subtask #4
0.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 1 ms 2652 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 2 ms 2652 KB Output is correct
12 Correct 2 ms 3164 KB Output is correct
13 Correct 1 ms 2652 KB Output is correct
14 Correct 1 ms 2908 KB Output is correct
15 Correct 1 ms 2760 KB Output is correct
16 Runtime error 4 ms 5976 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #5
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct
6 Correct 1 ms 2812 KB Output is correct
7 Correct 1 ms 2652 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 48 ms 26568 KB Output is correct
10 Correct 2 ms 2648 KB Output is correct
11 Correct 1 ms 3164 KB Output is correct
12 Correct 28 ms 21652 KB Output is correct
13 Correct 1 ms 2648 KB Output is correct
14 Correct 2 ms 3164 KB Output is correct
15 Correct 66 ms 29564 KB Output is correct
16 Correct 1 ms 2652 KB Output is correct
17 Correct 1 ms 2904 KB Output is correct
18 Correct 1 ms 2624 KB Output is correct
19 Correct 1 ms 2652 KB Output is correct
20 Correct 2 ms 3164 KB Output is correct
21 Correct 28 ms 21724 KB Output is correct
22 Correct 1 ms 2652 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 34 ms 13552 KB Output is correct
25 Correct 2 ms 2652 KB Output is correct
26 Runtime error 4 ms 5724 KB Execution killed with signal 6
27 Halted 0 ms 0 KB -