제출 #1300572

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300572		PieArmy	Team Coding (EGOI24_teamcoding)	C++20	12 / 100	64 ms	26252 KiB

Main

#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

struct Fen{
	int n;
	vector<int>tree;
	void init(int N){
		n=N;
		tree.resize(n+1,0);
	}
	void update(int tar,int x){
		while(tar<=n){
			tree[tar]+=x;
			tar+=(tar&-tar);
		}
	}
	int query(int tar){
		int res=0;
		while(tar>0){
			res+=tree[tar];
			tar-=(tar&-tar);
		}
		return res;
	}
};

int s=75;
int n,k;
int arr[100023];
vector<int>renk[100023],deps[100023];
vector<int>child[100023];
int in[100023],out[100023];
int dep[100023],h[100023];
int tim=0;
pair<int,int>res[100023];
pair<int,int>ans;

void dfs(int pos){
	in[pos]=++tim;
	deps[dep[pos]].pb(pos);
	for(int x:child[pos]){
		dep[x]=dep[pos]+1;
		dfs(x);
		h[pos]=max(h[pos],h[x]+1);
	}
	out[pos]=tim;
}

int main(){
	ios_base::sync_with_stdio(23^23);cin.tie(NULL);
	cin>>n>>k;
	ans={-1,0};
	for(int i=1;i<=n;i++){
		res[i]={-1,0};
		cin>>arr[i];
		arr[i]++;
		renk[arr[i]].pb(i);
	}
	for(int i=2;i<=n;i++){
		int x;cin>>x;x++;
		child[x].pb(i);
	}
	dfs(1);
	for(int o=1;o<=k;o++){
		if(!renk[o].size())continue;
		sort(renk[o].begin(),renk[o].end(),[&](const int &x,const int &y){
			return in[x]<in[y];
		});
		if(renk[o].size()>s){
			vector<int>roots;
			int mxout=0;
			for(int x:renk[o]){
				if(in[x]>mxout){
					roots.pb(x);
				}
				mxout=max(mxout,out[x]);
			}
			sort(roots.begin(),roots.end(),[&](const int &x,const int &y){
				return dep[x]+h[x]>dep[y]+h[y];
			});
			int l=0,r=0;
			for(int i=n-1;i>0;i--){
				int cnt=0;
				for(int x:deps[i]){
					if(arr[x]==o){
						cnt++;
					}
				}
				while(r<roots.size()&&dep[roots[r]]+h[roots[r]]>=i){
					r++;
				}
				while(l<roots.size()&&dep[roots[l]]>=i){
					l++;
				}
				int l2=0,r2=0;
				int var=0;
				for(int j=l;j<r;j++){
					while(r2<deps[i].size()&&in[deps[i][r2]]<=out[roots[j]]){
						if(arr[deps[i][r2]]==o)var++;
						r2++;
					}
					while(l2<r2&&in[deps[i][l2]]<in[roots[j]]){
						if(arr[deps[i][l2]]==o)var--;
						l2++;
					}
					int top=r2-l2;
					res[roots[j]].fr-=min(top,cnt);
					res[roots[j]].sc+=max(0,min(top-var,cnt-var));
					ans=min(ans,res[roots[j]]);
				}
			}
		}
		else{
			vector<int>v;
			for(int i=0;i<renk[o].size();i++){
				for(int j=i+1;j<renk[o].size();j++){
					if(dep[renk[o][j]]<=dep[renk[o][i]])continue;
					v.pb(renk[o][j]);
					if(j+1==renk[o].size()||dep[renk[o][j+1]]!=dep[renk[o][j]]){
						int var=0,top=0;
						int cnt=v.size();
						for(int x:v){
							if(in[x]>=in[renk[o][i]]&&in[x]<=out[renk[o][i]])var++;
						}
						int l=0,r=deps[dep[v.back()]].size();
						while(l<r){
							int mi=(l+r)/2;
							int x=deps[dep[v.back()]][mi];
							if(in[x]>=in[renk[o][i]])r=mi;
							else l=mi+1;
						}
						top-=l;
						l=0;r=deps[dep[v.back()]].size();
						while(l<r){
							int mi=(l+r)/2;
							int x=deps[dep[v.back()]][mi];
							if(in[x]>out[renk[o][i]])r=mi;
							else l=mi+1;
						}
						top+=l;
						res[renk[o][i]].fr-=min(top,cnt);
						res[renk[o][i]].sc+=max(0,min(top-var,cnt-var));
						v.clear();
					}
				}
				//cout<<renk[o][i]<<": "<<-res[renk[o][i]].fr<<" "<<res[renk[o][i]].sc<<endl;
				ans=min(ans,res[renk[o][i]]);
			}
		}
	}
	cout<<-ans.fr<<" "<<ans.sc<<endl;
}

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