Submission #404262

#	Time	Username	Problem	Language	Result	Execution time	Memory
404262		jamezzz	족보 (KOI18_family)	C++14	100 / 100	435 ms	63704 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;

struct rng{ int num,t,u; };

int n[2],k,p,num[2][300005],rep[2][300005],par[300005],sz[300005];
vi AL[2][300005];
vector<rng> rngs;

void dfs(int t,int u){
	if(u!=0&&u<=k){
		num[t][u]=1;
		rep[t][u]=u;
	}
	for(int v:AL[t][u]){
		dfs(t,v);
		num[t][u]+=num[t][v];
		rep[t][u]=rep[t][v];
	}
	if(num[t][u]>1)rngs.push_back({num[t][u],t,u});
}

int fp(int i){
	return (par[i]==i)?i:par[i]=fp(par[i]);
}

void join(int x,int y){
	x=fp(x),y=fp(y);
	if(x==y)return;
	if(sz[x]<sz[y])swap(x,y);
	par[y]=x;sz[x]+=sz[y];
}

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);
		}
	}
	dfs(0,0);dfs(1,0);
	sort(all(rngs),[&](rng a,rng b){return a.num<b.num;});
	for(int i=1;i<=k;++i){
		par[i]=i;sz[i]=1;
	}
	for(rng r:rngs){
		for(int v:AL[r.t][r.u]){
			join(rep[r.t][r.u],rep[r.t][v]);
		}
		if(sz(AL[r.t][r.u])<=1)continue;
		if(sz[fp(rep[r.t][r.u])]!=r.num){
			pf("NO\n");
			return 0;
		}
	}
	pf("YES\n");
}

Compilation message (stderr)

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

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