Submission #1188782

#TimeUsernameProblemLanguageResultExecution timeMemory
1188782tamir1Team Coding (EGOI24_teamcoding)C++20
0 / 100
4094 ms11336 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e5; int n, k, a[N + 5], p[N + 5], cnt[2], c, depth[N + 5], clr[N + 5], dar, x[N + 5], y[N + 5], mx, moves, d; vector<int> v[N + 5]; void dfs(int x) { for(int i : v[x]) { depth[i] = depth[x] + 1; dfs(i); } } void dfs1(int z) { int s = depth[z]; d = max(d, s); x[s]++; if(a[z] == c) y[s]++; for(int i : v[z]) { dfs1(i); } } int main() { ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); cin >> n >> k; for(int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]]++; } //N for(int i = 1; i < n; i++) { cin >> p[i]; v[p[i]].push_back(i); } //N c = (cnt[0] < cnt[1] ? 1 : 0); dfs(0); //N for(int i = 0; i < n; i++) { if(a[i] == c) { clr[depth[i]]++; } } //N for(int i = 0; i < n; i++) { if(clr[i]) { dar = i; break; } } for(int i = 0; i < n; i++) { //N if(depth[i] == dar) { d = n - 1; dfs1(i); int tmp1 = 0, tmp2 = 0; for(int j = 0; j <= d; j++) { if(clr[j] >= x[j]) { tmp1 += x[j]; tmp2 += x[j] - y[j]; } else { tmp1 += clr[j]; tmp2 += max(0, clr[j] - y[j]); } x[j] = 0; y[j] = 0; } if(mx < tmp1) { mx = tmp1; moves = tmp2; } else if(mx == tmp1) { if(moves > tmp2) moves = tmp2; } } } if(mx <= cnt[a[0]]) { mx = cnt[a[0]]; moves = 0; } cout << mx << " " << moves << "\n"; }
#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...