Submission #981088

#	Time	Username	Problem	Language	Result	Execution time	Memory
981088		midi	Beech Tree (IOI23_beechtree)	C++17	Compilation error	0 ms	0 KiB

beechtree

#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define vc vector
typedef vc<ll> vcll;
typedef vc<bool> vcb;
#define pr pair
typedef pr<ll, ll> prll;
typedef map<ll,ll> mapll;
#define umap unordered_map
typedef umap<ll,ll> umapll;

#define f0r(i,a,n) for ((i)=(a); (i)<=(n); (i)++)
#define r0f(i,n,a) for ((i)=(n); (i)>=(a); (i)--)

#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front
#define mp make_pair
#define fi first
#define se second
#define sz size
#define all(x) (x).begin(), (x).end()
#define all0(x, n) (x).begin(), (x).begin()+n
#define all1(x, n) (x).begin()+1, (x).begin()+n+1
#define allrev(x) (x).rbegin(), (x).rend()
#define in(v, s) ((s).find((v)) != (s).end())
#define GCD(x, y) __gcd(abs((x)), abs((y)))

#define INF (LLONG_MAX>>3ll)
#define MOD (1'000'000'007ll)

#define mxN (200'010ll)

inline void maxa(ll &a, ll b) { if (a<b) a=b; }
inline void mina(ll &a, ll b) { if (a>b) a=b; }

ll n, m;
vc<int> ans(mxN);
vcll par(mxN), clr(mxN);
vc<vcll> gr(mxN);

ll root;
vcb nds(mxN);
vc<vcll> clr_nds(mxN);
vc<vcll> sz_clrs(mxN);

void build_nds (ll u)
{
	nds[u]=1;
	for (const ll &v:gr[u]) build_nds(v);
}
void build_nds()
{
	nds.assign(n+5, 0);
	build_nds(root);
	nds[root]=0;
}

bool check (vcll &ar)
{
	ll last=INF;
	for (const ll &v:ar)
	{
		if (v==last) return 0;
		last=v;
	}
	return 1;
}

bool check_clr_nds()
{
	ll c;
	f0r(c,1,m) if (!check(clr_nds[c])) return 0;
	return 1;
}

bool build_clr_nds()
{
	ll u, c;
	clr_nds.assign(n+5, {});
	sz_clrs.assign(n+5, {});
	f0r(u,1,n) for (const ll &v:gr[u]) if (nds[v])
		clr_nds[clr[v]].pb(u);
	if (!check_clr_nds()) return 0;
	f0r(c,1,m) sz_clrs[clr_nds[c].sz()].pb(c);
	return 1;
}

void print (vcll &ar, string starter="")
{
	cout << starter << ": ";
	for (const ll &x:ar) printf("%lli ", x);
	printf("\n");
}

bool inside (ll sm, ll bg)
{
	// printf("\n");
	// print(clr_nds[sm], "sm");
	// print(clr_nds[bg], "bg");
	ll i=0, j=0;
	ll szi = clr_nds[sm].sz();
	ll szj = clr_nds[bg].sz();

	while (i<szi and j<szj)
	if (clr_nds[sm][i] == clr_nds[bg][i]) i++;
	else j++;

	return i==szi;
}

bool solve()
{
	clr_nds[mxN-4]={root};
	ll sz;
	ll lastc=mxN-5;
	f0r(sz,0,n) for (const ll &c:sz_clrs[sz])
	{
		if (!inside (lastc, c)) return 0;
		if (clr_nds[c].sz() and !inside (mxN-4, c)) return 0;
		lastc=c;
	}

	return 1;
}

void print_nds()
{
	ll u;
	printf("nds: ");
	f0r(u,1,n) if (nds[u]) printf("%lli ", u);
	printf("\n");
}

void print_clr_nds()
{
	ll c;
	f0r(c,1,m)
	{
		printf("clr_nds[%lli]", c);
		print (clr_nds[c]);
	}
}

bool calc (ll u)
{
	root=u;
	build_nds();
	// print_nds();
	if (!build_clr_nds()) return 0;
	// print_clr_nds();
	// print_clr_nds();
	return solve();
}

void brute (ll u)
{
	ans[u] = calc(u);
	for (const ll &v:gr[u]) brute(v);
}

void brute() { brute(1); }

vc<int> beechtree (int N, int M, vc<int> &PAR, vc<int> &CLR)
{
	n=N, m=M;
	ll i;
	f0r(i,1,n) par[i]=PAR[i-1]+1, clr[i]=CLR[i-1];
	par[1]=0;
	f0r(i,1,n) gr[par[i]].pb(i);

	clr_nds[mxN-5].clear();

	brute();

	f0r(i,1,n) ans[i-1]=ans[i];
	return ans;
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccAcek8f.o: in function `main':
grader.cpp:(.text.startup+0x27d): undefined reference to `beechtree(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status