#include <bits/stdc++.h>
using namespace std;
// compute for each node the set of leaf-descendants (bitmask)
void dfs_leaves(int u, int parent,
const vector<vector<int>>& adj,
int K,
vector<int>& leaf_mask,
vector<int>& out_mask)
{
int mask = 0;
bool isLeaf = true;
for (int v: adj[u]) if (v != parent) {
isLeaf = false;
dfs_leaves(v, u, adj, K, leaf_mask, out_mask);
mask |= out_mask[v];
}
if (isLeaf) {
// leaves are 1..K
mask = (1 << (u-1));
}
out_mask[u] = mask;
}
// check if every cluster in tree T appears among clusters of tree O
bool clusters_subset(const vector<int>& clustersT,
const unordered_set<int>& clustersO)
{
for (int c: clustersT) {
if (!clustersO.count(c)) return false;
}
return true;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N1, N2, K;
cin >> N1 >> N2 >> K;
vector<int> P1(N1+1), P2(N2+1);
for(int i=1;i<=N1;i++) cin>>P1[i];
for(int i=1;i<=N2;i++) cin>>P2[i];
// build adjacency for S and T
vector<vector<int>> adjS(N1+1), adjT(N2+1);
int rootS=0, rootT=0;
for(int i=1;i<=N1;i++){
if(P1[i]==0) rootS = i;
else { adjS[i].push_back(P1[i]);
adjS[P1[i]].push_back(i);
}
}
for(int i=1;i<=N2;i++){
if(P2[i]==0) rootT = i;
else { adjT[i].push_back(P2[i]);
adjT[P2[i]].push_back(i);
}
}
// Precompute T's clusters
vector<int> outT(N2+1), leaf_maskT(N2+1,0);
dfs_leaves(rootT,0,adjT,K,leaf_maskT,outT);
vector<int> clustersT;
for(int u=1;u<=N2;u++){
if(outT[u]!=0 && u>K) // only internal
clustersT.push_back(outT[u]);
}
// Gather the list of internal edges in S we might split
vector<pair<int,int>> intEdges;
for(int v=1;v<=N1;v++){
if(v>K && P1[v]>0 && P1[v]>K){
// both parent and v are internal => a candidate edge
intEdges.emplace_back(P1[v], v);
}
}
int M = intEdges.size();
bool ok = false;
// We'll iterate all 2^M ways to split or not split each internal edge
for(int mask=0; mask < (1<<M) && !ok; ++mask){
// Build a refined tree of S
int nextId = N1+1;
vector<vector<int>> adjO = adjS;
// For each bit=1 in mask, split that edge
for(int b=0;b<M;b++){
if(mask & (1<<b)){
auto [u,v] = intEdges[b];
// remove edge u-v
adjO[u].erase(find(adjO[u].begin(), adjO[u].end(), v));
adjO[v].erase(find(adjO[v].begin(), adjO[v].end(), u));
// add new node w
int w = nextId++;
adjO.resize(nextId);
// connect u-w and w-v
adjO[u].push_back(w); adjO[w].push_back(u);
adjO[w].push_back(v); adjO[v].push_back(w);
}
}
// compute clusters in O
vector<int> outO(nextId), leaf_maskO(nextId,0);
dfs_leaves(rootS, 0, adjO, K, leaf_maskO, outO);
unordered_set<int> allClustersO;
for(int u=1;u<nextId;u++){
if(outO[u]!=0 && u>K)
allClustersO.insert(outO[u]);
}
// check if T's clusters are subset
if(clusters_subset(clustersT, allClustersO)){
ok = true;
break;
}
}
cout << (ok ? "YES\n" : "NO\n");
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |