| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 981084 | midi | 참나무 (IOI23_beechtree) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
vcb 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); }
vcb 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;
}
void output (vcb &answer, ll N)
{
ll u;
f0r(u,1,N) printf("ans[%lli]: %lli\n", u, (ll)answer[u]);
}