제출 #288745

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288745		dorijanlendvaj	Cat in a tree (BOI17_catinatree)	C++14	51 / 100	1094 ms	82360 KiB

catinatree

//DUEL
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcount
#define popcntll __builtin_popcountll
#define all(a) begin(a),end(a)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

void compress(vi&v)
{
	set<int> s;
	for (auto a: v) s.insert(a);
	vi o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

void compress(vl&v)
{
	set<ll> s;
	for (auto a: v) s.insert(a);
	vl o(all(s));
	for (auto&a: v) a=lower_bound(all(o),a)-o.begin();
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
const int N=200010,M=1<<18;
int t,n,d,updit,md[N],radd,rmax,gv,abeg,upde;
vi ch1[N];

struct custom_hash
{
	int operator()(int x) const
	{
		return (x*1ll*x*326572+x*1ll*6782272823+28376387212871ll)%MOD;
	}
};

struct dpv
{
	//update: range add (done)
	//query: range maximum (done)
	//query: get value of 1 (done)
	//update: add x to beginning (done)
	//update: change element
	int off,kra,vvl;
	gp_hash_table<int,int,custom_hash> seg,pro;
	int size()
	{
		return kra-off;
	}
	void pr(int i)
	{
		if (pro.find(i)==pro.end()) return;
		if (seg.find(i)!=seg.end()) seg[i]+=pro[i];
		else seg.insert({i,pro[i]});
		if (i<M)
		{
			if (pro.find(i*2)!=pro.end()) pro[i*2]+=pro[i];
			else pro.insert({i*2,pro[i]});
			if (pro.find(i*2+1)!=pro.end()) pro[i*2+1]+=pro[i];
			else pro.insert({i*2+1,pro[i]});
		}
		pro[i]=0;
	}
	void upd(int l,int r,int x,int lo,int hi,int i)
	{
		++updit;
		if (lo>=l && hi<=r)
		{
			if (pro.find(i)!=pro.end()) pro[i]+=x;
			else pro.insert({i,x});
			pr(i);
			return;
		}
		pr(i);
		if (lo>=r || hi<=l) return;
		int mid=(lo+hi)/2;
		upd(l,r,x,lo,mid,i*2);
		upd(l,r,x,mid,hi,i*2+1);
		int s1=0,s2=0;
		if (seg.find(i*2)!=seg.end()) s1=seg[i*2];
		if (seg.find(i*2+1)!=seg.end()) s2=seg[i*2+1];
		if (seg.find(i)!=seg.end()) seg[i]=max(s1,s2);
		else seg.insert({i,max(s1,s2)});
	}
	void rangeAdd(int l,int r,int x)
	{
		++radd;
		l+=off;
		r+=off;
		assert(r<=kra);
		if (r==M) vvl+=x,--r;
		if (l==r) return;
		upd(l,r,x,0,M,1);
	}
	int ge(int l,int r,int lo,int hi,int i)
	{
		pr(i);
		if (lo>=l && hi<=r)
		{
			if (seg.find(i)!=seg.end()) return seg[i];
			else return 0;
		}
		if (lo>=r || hi<=l) return 0;
		int mid=(lo+hi)/2;
		return max(ge(l,r,lo,mid,i*2),ge(l,r,mid,hi,i*2+1));
	}
	int rangeMax(int l,int r)
	{
		++rmax;
		l+=off;
		r+=off;
		assert(r<=kra);
		bool ovokr=(r==M);
		int res=ge(l,min(r,M-1),0,M,1);
		if (ovokr) return max(res,vvl);
		else return res;
	}
	int getVal(int i)
	{
		i+=off;
		if (i==M-1) return vvl;
		++gv;
		vi v;
		i+=M;
		while (i)
		{
			v.pb(i);
			i/=2;
		}
		reverse(all(v));
		for (auto a: v) pr(a);
		i=v.back();
		if (seg.find(i)!=seg.end())
		{
			return seg[i];
		}
		else
		{
			return 0;
		}
	}
	void updVal(int i,int x)
	{
		i+=off;
		if (i==M-1)
		{
			vvl+=x;
			return;
		}
		++upde;
		vi v;
		i+=M;
		while (i)
		{
			v.pb(i);
			i/=2;
		}
		reverse(all(v));
		for (auto a: v) pr(a);
		i=v.back();
		if (seg.find(i)!=seg.end()) seg[i]=x;
		else seg.insert({i,x});
		for (i/=2;i;i/=2)
		{
			int s1=0,s2=0;
			if (seg.find(i*2)!=seg.end()) s1=seg[i*2];
			if (seg.find(i*2+1)!=seg.end()) s2=seg[i*2+1];
			if (seg.find(i)!=seg.end()) seg[i]=max(s1,s2);
			else seg.insert({i,max(s1,s2)});
		}
	}
	void insBeg(int x)
	{
		++abeg;
		--off;
		if (x) updVal(0,x);
	}
	void pop_back()
	{
		//updVal(kra-off-1,0);
		--kra;
	}
	void clear()
	{
		off=M-1;
		kra=M;
		vvl=1;
		seg.clear();
		pro.clear();
		//updVal(0,1);
	}
	void print()
	{
		cout<<size()<<endl;
		for (int i=0;i<size();++i) cout<<getVal(i)<<' '<<flush;
		cout<<endl;
	}
	dpv()
	{
		off=M-1;
		kra=M;
		vvl=1;
		//updVal(0,1);
	}
};

dpv dp;

void mer(dpv&a,dpv b)
{
	assert(a.size()>=b.size());
	vector<pii> ev; //time, +x if x is added, -x if x is removed
	for (int j=0;j<b.size();++j)
	{
		if (d-j<j)
		{
			int bj=b.getVal(j);
			//cout<<"on "<<j<<" there's "<<bj<<endl;
			if (bj>0)
			{
				ev.eb(d-j,bj);
				ev.eb(j,-bj);
			}
		}
		if (max(j,d-j)<a.size())
		{
			int maxd=a.rangeMax(max(j,d-j),a.size())-a.getVal(j)+b.getVal(j);
			//for (int i=max(j,d-j);i<(int)a.size();++i) c[j]=max(c[j],a[i]+b[j]);
			/*cout<<"from "<<max(j,d-j)<<" onward: "<<a.rangeMax(max(j,d-j),a.size())<<endl;
			cout<<"on a's "<<j<<" there's "<<a.getVal(j)<<endl;
			cout<<"on b's "<<j<<" there's "<<b.getVal(j)<<endl;*/
			if (maxd>0)
			{
				ev.eb(j,maxd);
				ev.eb(j+1,-maxd);
			}
		}
	}
	for (int j=0;j<b.size();++j)
	{
		int aj=a.getVal(j),bj=b.getVal(j);
		if (bj>aj)
		{
			ev.eb(j,bj-aj);
			ev.eb(j+1,aj-bj);
		}
	}
	sort(all(ev));
	int la=0;
	multiset<int> ms;
	for (auto x: ev)
	{
		if (x.x!=la && ms.size())
		{
			//cout<<"adding "<<*ms.rbegin()<<" to ["<<la<<","<<x.x<<")."<<endl;
			a.rangeAdd(la,x.x,*ms.rbegin());
		}
		la=x.x;
		if (x.y>0) ms.insert(x.y);
		else ms.erase(ms.find(-x.y));
	}
}

void dfs1(int i)
{
	for (auto a: ch1[i])
	{
		dfs1(a);
		md[i]=max(md[i],md[a]+1);
	}
}

void dfs(int i)
{
	dp.clear();
	//cout<<"a"<<i<<endl;
	vector<dpv> dps;
	//cout<<"b"<<i<<endl;
	int mad=-1;
	for (auto a: ch1[i]) if (mad==-1 || md[mad]<md[a]) mad=a;
	if (mad==-1)
	{
		dp=dpv();
		return;
	}
	//cout<<"c"<<i<<endl;
	for (auto a: ch1[i]) if (a!=mad)
	{
		dfs(a);
		/*cout<<"just visited "<<a<<endl;
		cout<<"dp:"<<endl;
		dp.print();
		cout<<endl;*/
		dp.insBeg(0);
		dps.pb(dp);
	}
	//cout<<"d"<<i<<endl;
	dfs(mad);
	int dod;
	if (dp.size()==d) dod=dp.getVal(d-1);
	else dod=0;
	//cout<<"e"<<i<<endl;
	dp.insBeg(dod+1);
	/*cout<<i<<en;
	dp.print();
	cout<<endl;*/
	//cout<<"f"<<i<<endl;
	for (auto a: dps) mer(dp,a);
	//cout<<"g"<<i<<endl;
	if (dp.size()>d)
	{
		assert(dp.size()==d+1);
		int x=dp.getVal(d),y=dp.getVal(d-1);
		//cout<<"got "<<x<<' '<<y<<endl;
		dp.pop_back();
		//cout<<"popped back"<<endl;
		if (x>y) dp.updVal(d-1,x);
	}
	/*cout<<i<<en;
	dp.print();
	cout<<endl;*/
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)[phone]);
	cin>>n>>d;
	//n=200000;
	//d=10000;
	for (int i=1;i<n;++i)
	{
		int a=0;
		cin>>a;
		ch1[a].pb(i);
	}
	dfs1(0);
	dfs(0);
	cout<<dp.rangeMax(0,dp.size())<<en;
	//cout<<radd<<' '<<rmax<<' '<<gv<<' '<<abeg<<' '<<upde<<' '<<updit<<endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 0 / 49