Submission #162649

#	Time	Username	Problem	Language	Result	Execution time	Memory
162649		MvC	Cat in a tree (BOI17_catinatree)	C++11	11 / 100	900 ms	888 KiB

catinatree

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int n,d,i,x,rs=1,nr;
bitset<1502>b[1502],v;
vector<int>rnd,a[1502];
void dfs(int x,int p,int pp,int l)
{
	if(l>=d)b[pp][x]=1;
	for(int i=0;i<(int)a[x].size();i++)if(a[x][i]!=p)dfs(a[x][i],x,pp,l+1);
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	srand(time(0));
	cin>>n>>d;
	for(i=2;i<=n;i++)
	{
		cin>>x;
		x++;
		a[x].pb(i);
		a[i].pb(x);
	}
	for(i=1;i<=n;i++)dfs(i,i,i,0);
	for(i=1;i<=n;i++)rnd.pb(i);
	while (clock() / (double) CLOCKS_PER_SEC <= 0.9)
	{
		random_shuffle(rnd.begin(),rnd.end());
		v.reset();
		nr=0;
		for(i=0;i<n;i++)
		{
			x=rnd[i];
			if((b[x]&v)==v)
			{
				nr++;
				v[x]=1;
			}
		}
		rs=max(rs,nr);
	}
	cout<<rs<<endl;
	return 0;
}

Compilation message (stderr)

catinatree.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
catinatree.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

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