Submission #1122574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122574		taichi123	Team Coding (EGOI24_teamcoding)	C++20	62 / 100	4096 ms	29376 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define fi first
#define se second
#define __builtin_popcount __builtin_popcountll
#define sz(v) ((int)(v).size()) 
#define mask(i) (1LL << (i))
#define getbit(mask, i) (((mask) >> (i)) & 1LL)
#define all(v) (v).begin(), (v).end()

template<typename X> void db(X x) { cerr << x << "] "; }
template<typename X, typename ...Y> void db(X x, Y... y) { cerr << x << ", "; db(y...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << ": ", db(__VA_ARGS__), cerr << "\n";
template <class T1, class T2> bool maximize(T1 &a, T2 &b) { return a < b ? a = b, 1 : 0; }
template <class T1, class T2> bool minimize(T1 &a, T2 &b) { return a > b ? a = b, 1 : 0; }
    
#define TASK "code"    
void solve();
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
//    if (fopen(TASK".inp", "r"))   {
//        freopen(TASK".inp", "r", stdin);
//        freopen(TASK".out", "w", stdout);
//    }   
    int tc = 1, d = 0; 
    // cin >> tc;
    while(tc--) {
        ++d;
        // cout << "Case #" << d << ": ";
        solve();
    }
    return 0;
}

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 2e5 + 5;

int n, k;
int h[N], col[N];
vector <int> adj[N];
vector <int> ds[N];
vector <int> a[N];

namespace sub34 {
    const int MAXL = 1e5;
    int id[N], tin[N], cnt[N];
    int timer;
    pair <int, int> ans = {-1, 0};
    
    void Max(pair<int, int> &a, pair <int, int> b) {
        if(a.fi < b.fi) a = b;
        else if(a.fi == b.fi) a.se = min(a.se, b.se);
    }
    void dfs(int u, int p) {
        id[u] = tin[u] = ++timer;
        for (auto v : adj[u]) if(v != p) {
            h[v] = h[u] + 1;
            dfs(v, u);
            id[u] = id[v];
        }
    }
    
    void dfs1(int u, int p) {
        for (auto v : adj[u]) if(v != p) {
            dfs1(v, u);
            if(sz(a[u]) < sz(a[v])) {
                swap(a[u], a[v]);
            }
            for (int i = sz(a[v]) - 1, j = sz(a[u]) - 1; i >= 0; i--, j--) {
                a[u][j] += a[v][i];
            }
        }
        a[u].push_back(1);
        if (sz(ds[col[u]]) <= MAXL) {
            int c = 0, k = 0;
            for (auto v : ds[col[u]]) {
                int d = sz(a[u]) - 1 - (h[v] - h[u]);   
                k += (tin[v] >= tin[u] && tin[v] <= id[u]);
                if (d >= 0 && d < sz(a[u]) && cnt[d] < a[u][d]) {
                    cnt[d]++, c++;
                }   
            }   
            Max(ans, {c, c - k});
            for (auto v : ds[col[u]]) {
                int d = sz(a[u]) - 1 - (h[v] - h[u]);
                if (d >= 0 && d < sz(a[u])) cnt[d] = 0;
            }
        }
    }   
    
    void solve() {
        dfs(1, 0); dfs1(1, 0);
        cout << ans.fi << ' ' << ans.se;
    }
}

namespace sub1 {
    int cnt[N];
    void solve() {
        for (int i = 1; i <= n; ++i) {
            cnt[col[i]]++;
        }
        int ans = 0;
        for (int i = 0; i < k; ++i) ans = max(ans, cnt[i]);
        cout << ans << " 0\n";
    }
}
void solve() {
    cin >> n >> k;
    for (int i = 1; i <= n; ++i) {
        cin >> col[i];
        ds[col[i]].push_back(i);
    }
    bool checksub1 = 1;
    for (int i = 2; i <= n; ++i) {
        int u;
        cin >> u;
        ++u;
        if(u != i - 1) checksub1 = 0;
        adj[i].push_back(u);
        adj[u].push_back(i);
    }
    if(checksub1) return sub1::solve(), void();
    sub34::solve();
}

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