Submission #403452

#	Time	Username	Problem	Language	Result	Execution time	Memory
403452		jamezzz	족보 (KOI18_family)	C++14	17 / 100	19 ms	28492 KiB

family

#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <ext/rope>
using namespace __gnu_cxx;

typedef tree<long long, null_type, less<long long>,
rb_tree_tag, tree_order_statistics_node_update> pbds;
//less_equal for identical elements

#define DEBUG

#ifdef DEBUG
#define debug(...) printf(__VA_ARGS__);
#else
#define debug(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;

int n[2],k,p,rt[2];
bool use[300005];
vi AL[2][300005];
vi l[2][300005];

void dfs(int t,int u){
	if(u<=k)l[t][u].pb(u);
	for(int v:AL[t][u]){
		dfs(t,v);
		for(int x:l[t][v])l[t][u].pb(x);
	}
	sort(all(l[t][u]));
}

int main(){
	sf("%d%d%d",&n[0],&n[1],&k);
	for(int t=0;t<2;++t){
		for(int i=1;i<=n[t];++i){
			sf("%d",&p);
			AL[t][p].pb(i);
			if(p==0)rt[t]=i;
		}
	}
	for(int t=0;t<2;++t){
		dfs(t,rt[t]);
	}
	/*
	for(int t=0;t<2;++t){
		pf("%d:\n",t);
		for(int i=1;i<=n[t];++i){
			for(int x:l[t][i])pf("%d ",x);
			pf("\n");
		}
	}
	*/
	for(int i=1;i<=n[1];++i){
		bool found=false;
		for(int j=1;j<=n[0];++j){
			if(use[j])continue;
			if(sz(l[1][i])!=sz(l[0][j]))continue;
			bool pos=true;
			for(int x=0;x<sz(l[1][i]);++x){
				if(l[1][i][x]!=l[0][j][x])pos=false;
			}
			if(pos){
				use[j]=true;
				found=true;
				break;
			}
		}
		if(!found)pf("NO\n"),exit(0);
	}
	pf("YES\n");
	
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:56:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  sf("%d%d%d",&n[0],&n[1],&k);
      |    ^
family.cpp:59:6: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |    sf("%d",&p);
      |      ^

• Subtask 1: 17 / 17
• Subtask 2: 0 / 27
• Subtask 3: 0 / 15
• Subtask 4: 0 / 41