Submission #1188786

#TimeUsernameProblemLanguageResultExecution timeMemory
1188786tamir1Team Coding (EGOI24_teamcoding)C++20
0 / 100
15 ms8264 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 bfs(int x) { queue<int> q; q.push(x); while(!q.empty()) { int x = q.front(); q.pop(); for(int i : v[x]) { depth[i] = depth[x] + 1; q.push(i); } } } void bfs1(int z) { queue<int> q; q.push(z); while(!q.empty()) { int z = q.front(); q.pop(); int s = depth[z]; d = max(d, s); x[s]++; if(a[z] == c) y[s]++; for(int i : v[z]) { q.push(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]; // a[i] = 0; cnt[a[i]]++; } //N for(int i = 1; i < n; i++) { cin >> p[i]; // p[i] = i - 1; v[p[i]].push_back(i); } //N //c = (cnt[0] < cnt[1] ? 1 : 0); bfs(0); // for(int i = 0; i < n; i++) { // cout << depth[i] << " "; // } //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; bfs1(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...