Submission #1148441

#TimeUsernameProblemLanguageResultExecution timeMemory
1148441KaleemRazaSyedTeam Coding (EGOI24_teamcoding)C++20
100 / 100
74 ms42568 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10, S = 350; int n, k, a[N], ans, mi, occur[N], C[N], h[N]; vector<int> child[N]; set<int> vec[N]; map<int, int> cnt[N]; void bfs(int v) { queue<int> Q; Q.push(v); int X = 0; while(Q.size()) { int u = Q.front(); Q.pop(); X += (a[v] == a[u]); C[h[u]]++; for(int c : child[u]) Q.push(c); } int sol = 0; for(int i = h[v]; C[i] > 0; i++) { sol += min(C[i], cnt[a[v]][i]); C[i] = 0; } if(sol > ans) ans = sol, mi = sol - X; else if(sol == ans) mi = min(sol - X, mi); } void dfs(int v, int color) { if(a[v] == color) { bfs(v); return; } for(int c : child[v]) dfs(c, color); } void prejob(int v) { vec[a[v]].insert(h[v]); cnt[a[v]][h[v]] ++; for(int c : child[v]) { h[c] = h[v] + 1; prejob(c); } } int cc[N]; void dfs2(int v) { vector<int> sz; int X = cc[a[v]]; if(h[v] == *vec[a[v]].begin()) { for(int hv : vec[a[v]]) sz.push_back(C[hv]); } cc[a[v]]++; C[h[v]]++; for(int c : child[v]) dfs2(c); X = cc[a[v]] - X; if(h[v] == *vec[a[v]].begin()) { int i = 0; int sol = 0; for(int hv : vec[a[v]]) if(hv >= h[v]) { sol += min(C[hv] - sz[i], cnt[a[v]][hv]); i++; } if(sol > ans) ans = sol, mi = sol - X; else if(sol == ans) mi = min(mi, sol - X); } } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); cin >> n >> k; for(int i = 0; i < n; i ++) { cin >> a[i]; occur[a[i]]++; } cnt[a[0]][0]++; for(int i = 1; i < n; i ++) { int p; cin >> p; child[p].push_back(i); } prejob(0); for(int i = 0; i < k; i ++) if(occur[i] >= S) dfs(0, i); if(ans < S) dfs2(0); cout << ans << ' ' << mi << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...