oj.uz

Submission #329780

# Submission time Handle Problem Language Result Execution time Memory
329780 2020-11-22T13:34:51 Z oolimry None (KOI18_family) C++14
0 / 100
 1 ms 364 KB 
#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) b.size());
}

int main(){
	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";
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -