Submission #329958

#	Time	Username	Problem	Language	Result	Execution time	Memory
329958		oolimry	족보 (KOI18_family)	C++14	0 / 100	1 ms	492 KiB

family

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

struct tree{
	int n, k, root;
	
	vector<int> child[305];
	vector<int> stuff[305];
	int vis[305];
	void init(){
		for(int i = 1;i <= n;i++){
			vis[i] = false;
		}
	}
	
	void dfs(int u){
		if(vis[u]) return;
		vis[u] = true;
		
		if(u <= k){
			stuff[u] = {u};
			return;
		}
		
		for(int v : child[u]){
			dfs(v);
			for(int x : stuff[v]) stuff[u].push_back(x);
		}
	}
	
} A, B;

bool overlap(vector<int> a, vector<int> b){
	if((int) a.size() > (int) b.size()) swap(a,b);
	
	int cnt = 0;;
	sort(b.begin(), b.end()); b.push_back(123283293);
	for(int x : a){
		if(*lower_bound(b.begin(), b.end(), x) == x) cnt++;
	}
	
	return (cnt == 0) || (cnt == (int) a.size());
}

int main(){
	freopen("i.txt","r",stdin);
	int n1, n2, K; cin >> n1 >> n2 >> K;
	
	assert(n1 <= 300);
	A.n = n1, A.k = K;
	B.n = n2, B.k = K;
	
	for(int i = 1;i <= n1;i++){
		int a; cin >> a;
		A.child[a].push_back(i);
	}
	
	for(int i = 1;i <= n2;i++){
		int b; cin >> b;
		B.child[b].push_back(i);
	}
	
	for(int i = 1;i <= n1;i++) A.dfs(i);
	for(int i = 1;i <= n2;i++) B.dfs(i);
	
	for(int i = 1;i <= n1;i++){
		//for(int x : A.stuff[i]) cout << x << " "; cout << "\n";
		for(int j = 1;j <= n2;j++){
			if(!overlap(A.stuff[i], B.stuff[j])){
				cout << "NO";
				return 0;
			}
		}
	}
	cout << "YES";
}

Compilation message (stderr)

family.cpp: In function 'int main()':
family.cpp:46:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   46 |  freopen("i.txt","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~

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