Submission #1148476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148476		Faisal_Saqib	Team Coding (EGOI24_teamcoding)	C++20	100 / 100	1395 ms	95148 KiB

Main

#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; }
};
gp_hash_table<ll, ll,chash> 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 if(path_from_root.find(color[x])==path_from_root.end())
	{
	  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;
}

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