제출 #1200532

#제출 시각아이디문제언어결과실행 시간메모리
1200532AkibAzmain족보 (KOI18_family)C++20
0 / 100
3094 ms444 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...