Submission #1164602

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164602		nai0610	Beech Tree (IOI23_beechtree)	C++20	5 / 100	135 ms	33996 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
// 
const int maxn =2e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int sz[maxn],par[maxn],b[maxn],cnt[maxn],col[maxn],S[maxn];
vector<int> res;
bool vs[maxn];
vector<int> g[maxn],a;
struct nai{
	int s,id,u;
	bool operator<(const nai& other) const {
		return (s==other.s?id<other.id:s>other.s);
	}
};
set<nai> s;
int get(int u,int p=-1) {
	sz[u]=1;
	for (auto v:g[u]) {
		if (!vs[v]&&v!=p) sz[u]+=get(v,u);
	}
	return sz[u];
}
int find (int u,int s,int p=-1) {
	for (auto v:g[u]) {
		if (!vs[v]&&v!=p&&sz[v]*2>=s) return find(v,s,u);
	}
	return u;
}
int calc(int u){
	a.clear();
	s.insert({S[u],0,u});
	while (!s.empty()) {
		int x=s.begin()->u;
		s.erase(s.begin());
		a.push_back(x);
		for (auto v:g[x]) {
			if (v!=par[x]) s.insert({S[v],(int)a.size(),v});
		}
	}
	for (int i=1;i<a.size();i++) cnt[col[a[i]]]=0;
	for (int i=1;i<a.size();i++) {
		int x=(i==1?0:cnt[col[a[i]]]);
		if (par[a[i]]!=a[x]) return false;
		cnt[col[a[i]]]++;
	}
	return true;
}
void nai(int u) {
	int c=find(u,get(u));
	vs[c]=1;
	if (b[c]==-1){
		b[c]=calc(c);
		if (b[c]==0) {
			for (int v=par[c];v&&b[v]==-1;v=par[v]) b[v]=0;
		}
	}
	if (b[c]!=1) {
		for (auto v:g[c]) {
		  if (!vs[v]&&v!=par[c]) nai(v);
		}
	}
	if (par[c]&&!vs[par[c]]) nai(par[c]);
}
void dfs(int u,int p=-1) {
	S[u]=1;
	for (auto v:g[u]) {
		if (v!=p) {
			dfs(v,u);
			S[u]+=S[v];
		}
	}
}
vector<int> beechtree(int n,int m,vector<int> p,vector<int> c){
	for (int i=0;i<n;i++) {
		col[i+1]=c[i];
		par[i+1]=p[i]+1;
		if (par[i+1]) {
			g[par[i+1]].push_back(i+1);
			g[i+1].push_back(par[i+1]);
		}
	}
	res.resize(n);
	memset(b,-1,sizeof(b));
	dfs(1);
	nai(1);
	for (int i=1;i<=n;i++) {
		if (i>1&&b[par[i]]==1) b[i]=1;
		res[i-1]=b[i];
	}
	return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 5 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12