Submission #1220875

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220875		overwatch9	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	41 ms	23624 KiB

Main

// subtask 2
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 1;
int col[maxn];
vector <int> adj[maxn];
int grps[maxn][2];
void dfs(int s, int d) {
    grps[d][col[s]]++;
    for (auto i : adj[s]) {
        dfs(i, d+1);
    }
}
pair <int, int> ans;
pair <int, int> dp[maxn][2];
bool ready[maxn][2];
pair <int, int> get_best(pair <int, int> a, pair <int, int> b) {
    if (a.first > b.first)
        return a;
    if (b.first > a.first)
        return b;
    if (a.second < b.second)
        return a;
    return b;
}
pair <int, int> dfs2(int s, int c, int d) {
    if (ready[s][c])
        return dp[s][c];
    // find out the optimal answer if node s had to have color "c"
    pair <int, int> res = {0, 0};
    if (col[s] == c)
        res.first++;
    else if (grps[d][c] > 0) {
        res.first++;
        res.second++;
    }
    for (auto i : adj[s]) {
        pair <int, int> res2 = dfs2(i, c, d+1);
        res.first += res2.first;
        res.second += res2.second;
    }
    ans = get_best(ans, res);
    for (auto i : adj[s]) {
        pair <int, int> res2 = dfs2(i, 1-c, d+1);
        ans = get_best(ans, res2);
        res2 = dfs2(i, c, d+1);
        ans = get_best(ans, res2);
    }
    if (col[s] == c)
        ;
    else if (grps[d][c] > 0) {
        res.first--;
        res.second--;
    }
    ready[s][c] = true;
    dp[s][c] = res;
    return res;
}
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 p;
        cin >> p;
        adj[p].push_back(i);
    }
    dfs(0, 0);
    ans.first = 0;
    ans.second = 1e9;
    dfs2(0, 0, 0);
    dfs2(0, 1, 0);
    cout << ans.first << ' ' << ans.second << '\n';
}

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