제출 #1199465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1199465		cxijsijsjsyk	Team Coding (EGOI24_teamcoding)	C++20	0 / 100	4094 ms	1114112 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<cassert>
using namespace std;
vector<int> edges[100005];
pair<int, int> times[100005];
int depth[100005];
int col[100005]; int cnt = 1;
vector<int> depthtimes[100005];
vector<int> nwcol[100005];
map<int, int> dwcol[100005]; int maxd;
vector<int> ans; vector<int> ansind;
void dfs(int n, int d) {
	times[n].first = cnt++;
	depth[n] = d; maxd = max(maxd, d);
	for (auto c : edges[n]) {
		dfs(c, d+1);
	}
	times[n].second = cnt++;
}

void find(int n, int cl) {
	if (col[n] == cl) {
		int curans = 0;
		for (int i = depth[n]; i <= maxd; i++) {
			if (dwcol[cl][i]==0) continue;
			int up = upper_bound(depthtimes[i].begin(), depthtimes[i].end(), times[n].second)-depthtimes[i].begin();
			int low = lower_bound(depthtimes[i].begin(), depthtimes[i].end(), times[n].first)-depthtimes[i].begin();
			curans += min(up-low, dwcol[cl][i]);
		}
		if (ans.empty() || ans.back() < curans) {
			ans.clear(); ansind.clear();
			ans.push_back(curans); ansind.push_back(n);
		}
		return;
	}
	for (auto c : edges[n]) {
		find(c, cl);
	}
}

int final(int n, int cl) {
	int ret = 0;
	for (auto c : edges[n]) {
		ret += final(c, cl);
	}
	return col[n] == cl ? ret+1 : ret;
}

int main() {
	int n, k; cin>>n>>k;
	for (int i = 0; i < n; i++) cin>>col[i];
	
	for (int i = 1; i < n; i++) {
		int x; cin>>x;
		edges[x].push_back(i);
	}
	
	dfs(0, 0);
	for (int i = 0; i < n; i++) {
		depthtimes[depth[i]].push_back(times[i].first);
	}
	for (int i = 0; i <= n; i++) {
		sort(depthtimes[i].begin(), depthtimes[i].end());
	}
	
	for (int i = 0; i < n; i++) {
		dwcol[col[i]][depth[i]]++;
	}
	
	for (int i = 0; i < k; i++) {
		find(0, i);
	}
	int minv = 1e9;
	for (int i = 0; i < (int)ans.size(); i++) {
		minv = min(minv, final(ansind[i], col[ansind[i]]));
	}
	cout<<ans.back()<<" "<<ans.back()-minv<<endl;
	return 0;
	
	
	
	
	for (int i = 0; i < n; i++) {
		nwcol[col[i]].push_back(i);
	}

	int bestans = 0; int bestswap = 1e9;
	for (int i = 0; i < n; i++) {
		map<int, int> used;
		int curans = 0;
		int curswap = 0;
		for (auto j : nwcol[col[i]]) {
			if (j == i || depth[j] <= depth[i]) continue;
			int up = upper_bound(depthtimes[depth[j]].begin(), depthtimes[depth[j]].end(), times[i].second)-depthtimes[depth[j]].begin();
			int low = lower_bound(depthtimes[depth[j]].begin(), depthtimes[depth[j]].end(), times[i].first)-depthtimes[depth[j]].begin();
			assert(up-low>=0);
			if (up-low-used[depth[j]]>0) {
				used[depth[j]]++;
				curans++;
				if (times[i].first < times[j].first && times[j].second < times[i].second) {
					// enclosed
				}
				else curswap++;
			}
		}
		if (bestans == curans+1) {
			bestswap = min(bestswap, curswap);
		}
		else if (bestans < curans+1) {
			bestans = curans+1;
			bestswap = curswap;
		}
	}
	cout<<bestans<<" "<<bestswap<<endl;
} 

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