Submission #1156602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156602		beaconmc	Team Coding (EGOI24_teamcoding)	C++20	42 / 100	4119 ms	839612 KiB

Main

#include <bits/stdc++.h>
 
typedef int ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;


vector<basic_string<ll>> edges;
vector<ll> pref;

ll n,k;
ll timer = 0;
ll tin[100005];
ll tout[100005];
ll depth[100005];
unordered_map<ll, ll> stuff[100005];
vector<ll> depths[100005];
vector<ll> consider;
vector<ll> prefs[100005];

ll ans = -1, ans2 = 0;
void dfs(ll a, ll d){
	depths[d].push_back(a);
	depth[a] = d;
	stuff[d][pref[a]] += 1;
	tin[a] = timer;
	timer += 1;
	for (auto&i : edges[a]){
		dfs(i, d+1);
	}
	tout[a] = timer;
}

ll numchild(ll a, ll k){

	

	if (!(0<=k && k<100005)) return 0;
	vector<ll> &sus = depths[k];
	if (sus.size()==0) return 0;
	if (depth[a] == k) return 0;


	ll lo = 0;
	ll hi = sus.size()-1;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (tin[sus[mid]] >= tin[a]) hi = mid;
		else lo = mid+1;
	}
	ll leftp = lo;
	lo = 0;
	hi = sus.size()-1;
	while (lo<hi){
		ll mid = (lo+hi+1)/2;
		if (tout[sus[mid]] <= tout[a]) lo = mid;
		else hi = mid-1;
	}
	ll rightp = lo;


	if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a])) return 0;

	return max((ll)0,rightp-leftp+1);
}

ll numspecialchild(ll a, ll k, ll c){

	if (!(0<=k && k<100005)) return 0;
	vector<ll> &sus = depths[k];
	if (sus.size()==0) return 0;
	if (depth[a] == k) return 0;


	ll lo = 0;
	ll hi = sus.size()-1;
	while (lo<hi){
		ll mid = (lo+hi)/2;
		if (tin[sus[mid]] >= tin[a]) hi = mid;
		else lo = mid+1;
	}
	ll leftp = lo;
	lo = 0;
	hi = sus.size()-1;
	while (lo<hi){
		ll mid = (lo+hi+1)/2;
		if (tout[sus[mid]] <= tout[a]) lo = mid;
		else hi = mid-1;
	}
	ll rightp = lo;
	ll ans = 0;

	if (!(tin[a] <= tin[sus[leftp]] && tout[sus[leftp]] <= tout[a])) return 0;
	FOR(i,leftp, rightp+1){
		ans += (pref[sus[i]]==c);
	}

	return ans;


}

void solve(ll a){
	ll tans = 1;
	ll tans2 = 0;
	for (auto&i : consider){
		ll temp = numchild(a,i);
		if (temp==0) continue;
		tans += min(temp, stuff[i][pref[a]]);
		tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]);
	}

	if (tans > ans) ans = tans, ans2 = tans2;
	else if (tans == ans) ans2 = min(ans2, tans2);

}
void solve2(ll a){

	ll tans = 1;
	ll tans2 = 0;

	FOR(i, depth[a]+1, n){
		ll temp = numchild(a,i);
		if (temp==0) break;
		tans += min(temp, stuff[i][pref[a]]);
		tans2 += min(temp, stuff[i][pref[a]]) - numspecialchild(a, i, pref[a]);

	}

	if (tans > ans) ans = tans, ans2 = tans2;
	else if (tans == ans) ans2 = min(ans2, tans2);
}

void dfs2(ll a, ll p){

	if(pref[a] == p){
		solve2(a);
		return;
	}


	for (auto& i :edges[a]) dfs2(i,p);

}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    FOR(i,0,100005){
    	stuff[i].reserve(1<<10);
    	stuff[i].max_load_factor(0.25);

    }

	cin >> n >> k;

	FOR(i,0,n) edges.push_back({}), pref.push_back(0);

	FOR(i,0,n){
		cin >> pref[i];
		prefs[pref[i]].push_back(i);
	}
	FOR(i,1,n){
		ll temp;
		cin >> temp;

		edges[temp].push_back(i);
	}
	dfs(0,0);

	FOR(p,0,k){

		if (prefs[p].size() > 400) dfs2(0,p);
		else{
			
			consider.clear();
			unordered_set<ll> temps;
			temps.reserve(1<<18);
    		temps.max_load_factor(0.25);
			for (auto&i : prefs[p]) temps.insert(depth[i]);
			for (auto&i : temps)consider.push_back(i);

			for (auto&i : prefs[p]){
				solve(i);

			}
		}
	}

	cout << ans << " " << ans2 << endl;





}

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