Submission #1200532

#	Time	Username	Problem	Language	Result	Execution time	Memory
1200532		AkibAzmain	족보 (KOI18_family)	C++20	0 / 100	3094 ms	444 KiB

family

#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;
}

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