제출 #1199297

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

Main

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#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];
void dfs(int n, int d) {
	times[n].first = cnt++;
	depth[n] = d;
	for (auto c : edges[n]) {
		dfs(c, d+1);
	}
	times[n].second = cnt++;
}

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

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 < k; i++) {
		sort(depthtimes[i].begin(), depthtimes[i].end());
	}
	for (int i = 0; i < n; i++) {
		nwcol[col[i]].push_back(i);
	}
	int bestans = 0; int bestind = 0;
	for (int i = 0; i < n; i++) {
		map<int, int> used;
		int curans = 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();
			//if (up > depthtimes[depth[j]].size()) up--;
			int low = lower_bound(depthtimes[depth[j]].begin(), depthtimes[depth[j]].end(), times[i].first)-depthtimes[depth[j]].begin();
			assert(up-low>=0);
			//cout<<times[i].first<<" "<<times[i].second<<endl;
			//cout<<j<<" "<<low<<" "<<up<<endl;
			//cout<<up-low<<" with depth "<<depth[j]<<endl;
			if (up-low-used[depth[j]]>0) {
				used[depth[j]]++;
				curans++;
			}
		}
		if (bestans < curans+1) {
			bestans = curans+1;
			bestind = i;
		}
	}
	cout<<bestans<<" "<<bestans-fin(bestind, col[bestind])<<endl;
} 

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