Submission #1148682

#TimeUsernameProblemLanguageResultExecution timeMemory
1148682Faisal_SaqibTeam Coding (EGOI24_teamcoding)C++20
100 / 100
1779 ms53908 KiB
#include <bits/stdc++.h> using namespace std; const int N=1e5+10; vector<int> ma[N]; int h[N],sz[N],cnt[N],ans=0,color[N],cur_ans=0,n,k; // #include <bits/extc++.h> /** keep-include */ // // To use most bits rather than just the lowest ones: // // struct chash { // large odd number for C // // const ll C = ll(4e18 * acos(0)) | 71; // // ll operator()(ll x) const { return __builtin_bswap64(x*C); } // // }; // #define ll long long // using namespace __gnu_pbds; // const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count(); // struct chash { // ll operator()(ll x) const { return x ^ RANDOM; } // }; unordered_map<int,int> subtree_p[N],tree_p[N]; set<int> occur[N]; pair<int,int> maintain_ans[N]; vector<int> updated[N]; pair<int,int> min_ans={0,0}; set<int> colors_maintain; void dfs_sz(int x,int p=-1) { tree_p[h[x]][color[x]]++; sz[x]=1; occur[color[x]].insert(h[x]); for(auto y:ma[x]) { if(y==p)continue; h[y]=h[x]+1; dfs_sz(y,x); sz[x]+=sz[y]; } } int req_color; // ans_p+=subtree_p[h][color[x]]; // step_p+=min(cnt[h]-subtree_p[h][color[x]],tree_p[h][color[x]]-subtree_p[h][color[x]]); void rem_contro(int he,int co) { maintain_ans[co].first-=subtree_p[he][co]; maintain_ans[co].second-=min(cnt[ he]-subtree_p[he][co],tree_p[he][co]-subtree_p[he][co]); } void add_contro(int he,int co) { maintain_ans[co].first+=subtree_p[he][co]; maintain_ans[co].second+=min(cnt[he]-subtree_p[he][co],tree_p[he][co]-subtree_p[he][co]); } void adder(int x,int p) { // color[i] < K // if(color[x]<2) for(auto col:updated[h[x]]) { rem_contro(h[x],col); } cnt[h[x]]++; subtree_p[h[x]][color[x]]++; for(auto col:updated[h[x]]) { add_contro(h[x],col); } for(auto y:ma[x]) { if(y==p)continue; adder(y,x); } } void deleter(int x,int p) { // if(color[x]<2) for(auto col:updated[h[x]]) { rem_contro(h[x],col); } cnt[h[x]]--; subtree_p[h[x]][color[x]]--; for(auto col:updated[h[x]]) { add_contro(h[x],col); } for(auto y:ma[x]) { if(y==p)continue; deleter(y,x); } } set<int> path_from_root; void dfs(int x,int p=-1,bool keep=0) { path_from_root.insert(color[x]); int big=-1; for(auto y:ma[x]) { if(y==p)continue; if(big==-1 or sz[big]<sz[y]) big=y; } for(auto y:ma[x]) { if(y==p or y==big)continue; dfs(y,x); } // cur_ans=0; for(auto col:colors_maintain) { maintain_ans[col]={0,0}; } if(big!=-1) { dfs(big,x,1); } for(auto y:ma[x]) { if(y==p or y==big)continue; adder(y,x); } //Real solving part is this // cnt[color[x]]++; // ans=max(ans,cnt[color[x]]); path_from_root.erase(color[x]); for(auto col:updated[h[x]]) { rem_contro(h[x],col); } cnt[h[x]]++; subtree_p[h[x]][color[x]]++; for(auto col:updated[h[x]]) { add_contro(h[x],col); } if(colors_maintain.find(color[x])!=colors_maintain.end()) { min_ans=min(min_ans,{-maintain_ans[color[x]].first-maintain_ans[color[x]].second,maintain_ans[color[x]].second}); // min_ans=min(min_ans,{-maintain_ans[0].first-maintain_ans[0].second,maintain_ans[0].second}); // min_ans=min(min_ans,{-maintain_ans[1].first-maintain_ans[1].second,maintain_ans[1].second}); } else { int ans_p=0,step_p=0; // cout<<"NODe "<<x<<" caioo asL "; // for(int h=1;h<=n;h++) // either iterate over all height where their is atleast one of color[x]s for(int h:occur[color[x]]) // either iterate over all height where their is atleast one of color[x]s { ans_p+=subtree_p[h][color[x]]; // cout<<subtree_p[h][color[x]]<<' '<<h<<endl; step_p+=min(cnt[h]-subtree_p[h][color[x]],tree_p[h][color[x]]-subtree_p[h][color[x]]); // if(min(cnt[h]-subtree_p[h][color[x]],tree_p[h][color[x]]-subtree_p[h][color[x]])<0)cout<<"Error"<<endl; } min_ans=min(min_ans,{-ans_p-step_p,step_p}); } // cout<<endl; // if((ans_p+step_p)>4) // { // cout<<"Node "<<x<<' '<<-ans_p-step_p<<' '<<step_p<<endl; // } if(!keep) { deleter(x,p); } } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; for(int i=0;i<n;i++)cin>>color[i]; bool subtask=1; for(int i=1;i<n;i++) { int x=i,y; cin>>y; subtask&=(y==(x-1)); // cout<<y<<' '<<x<<endl; ma[y].push_back(x); } if(subtask) { map<int,int> apt; int mx=0; for(int i=n-1;i>=0;i--) mx=max(mx,++apt[color[i]]); cout<<mx<<' '<<0<<endl; return 0; } h[0]=1; dfs_sz(0); const int SQ=320; for(int i=0;i<k;i++) { if(occur[i].size()>SQ) { colors_maintain.insert(i); maintain_ans[i]={0,0}; for(auto h:occur[i]) { updated[h].push_back(i); } } } // for(int i=0;i<n;i++) // { // if(colors_maintain) // } dfs(0); cout<<-min_ans.first<<' '<<min_ans.second<<endl; }
#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...