Submission #1188833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188833		Batorgil952	Team Coding (EGOI24_teamcoding)	C++20	35 / 100	46 ms	10824 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair

using namespace std;

const int N=1e5+5;
int a[N], T[4000];
vector< int > v[N];
map< int, int > M;
int F[3003][3003];
int ans, mi;
int FF[4003], L[4003];

void Fun(int p){
	F[T[p]][a[p]]++;
	int vn=v[p].size();
	for(int i=0; i<vn; i++){
		T[v[p][i]]=T[p]+1;
		Fun(v[p][i]);
	}
}

void Rec(int p){
	int s, op, ma;
	queue< int > q;
	q.push(p);
	
	for(int i=1; i<=2000; i++){
		FF[i]=L[i]=0;
	}
	ma=T[p];
	while(!q.empty()){
		int x=q.front();
		q.pop();
		int vn=v[x].size();
//		cout<<x<<" "<<T[x]<<endl;
		FF[T[x]]++;
		if(a[x]==a[p]) L[T[x]]++;
		ma=max(ma, T[x]);
		for(int i=0; i<vn; i++){
			q.push(v[x][i]);
		}
	}
	s=0;
	op=0;
//	cout<<T[p]<<endl;
	for(int i=T[p]; i<=ma; i++){
		if(L[i]!=FF[i]){
			int av=F[i][a[p]]-L[i];
//			cout<<"		"<<i<<"   "<<av<<" "<<F[i][a[p]]<<" "<<a[p]<<" "<<FF[i]<<endl;
			if(av+L[i]<=FF[i]){
				L[i]+=av;
				op+=av;
			}
			else{
				op+=(FF[i]-L[i]);
				L[i]=FF[i];
			}
		}
//		cout<<"	L"<<L[i]<<endl;
		s+=L[i];
	}
//	cout<<"K "<<p<<" "<<s<<" "<<op<<endl;
	if(ans<s){
//		cout<<ans<<endl;
		ans=s;
//		cout<<ans<<endl;
		mi=op;
	}
	else if(ans==s){
		mi=min(mi, op);
	}
}

int main(){
	int n, k, i, x, anss, ind;
	
	scanf("%d",&n);
	scanf("%d",&k);
	
	for(i=0; i<n; i++){
		scanf("%d",&a[i]);
	}
	
	ind=0;
	for(i=1; i<n; i++){
		scanf("%d",&x);
		v[x].pb(i);
		if(i-x==1) ind++;
	}
	
	if(n<=2000){
		T[0]=0;
		Fun(0);
		ans=-1;
		mi=0;
		for(i=0; i<n; i++){
			Rec(i);
		}
		printf("%d %d\n", ans, mi);
		return 0;
	}
	else if(ind==n-1){
		anss=0;
		for(i=n-1; i>=0; i--){
			M[a[i]]++;
			anss=max(M[a[i]], anss);
		}
		printf("%d 0\n", anss);
		return 0;
	}
	 
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   80 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:81:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   81 |         scanf("%d",&k);
      |         ~~~~~^~~~~~~~~
Main.cpp:84:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |                 scanf("%d",&a[i]);
      |                 ~~~~~^~~~~~~~~~~~
Main.cpp:89:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   89 |                 scanf("%d",&x);
      |                 ~~~~~^~~~~~~~~

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