Submission #1143831

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143831		monkey133	Unique Cities (JOI19_ho_t5)	C++20	0 / 100	214 ms	43140 KiB

joi2019_ho_t5

#include <bits/stdc++.h>
using namespace std;
 
// --- GLOBAL DATA STRUCTURES ---
// We use 1-indexing for the cities.
int N, M;
vector<vector<int>> adj;      // tree: for each city, its adjacent cities
vector<int> speciality;       // speciality[i] is the speciality produced at city i
 
// --- MEMOIZATION FOR THE "CHAIN" (directed edge) ---
// For each directed edge (x -> u), we want to store the chain (as a vector<int>)
// defined by:
//   f(x,u)[1] = u,
//   and if (u, v) is the unique continuation (i.e. among u’s neighbors excluding x, if there is exactly one neighbor v)
//   then for d>=2: f(x,u)[d] = f(u,v)[d-1],
// otherwise the chain stops.
 
// We use a key for a directed edge.
struct EdgeKey {
    int u, v; // u -> v (starting at u then going to v)
    bool operator==(const EdgeKey &other) const {
        return u == other.u && v == other.v;
    }
};
 
struct EdgeKeyHash {
    std::size_t operator()(const EdgeKey &ek) const {
        return ((size_t)ek.u) * 100007ULL + ek.v;
    }
};
 
// memo: maps the directed edge (x -> u) to the chain vector.
unordered_map<EdgeKey, vector<int>, EdgeKeyHash> memo;
 
// Recursive function: getChain(x,u) returns the chain (as a vector<int>) for the directed edge x->u.
vector<int> getChain(int x, int u) {
    EdgeKey key = {x, u};
    if(memo.find(key) != memo.end())
        return memo[key];
    vector<int> chain;
    // The first city in the chain is u (at distance 1 from x).
    chain.push_back(u);
    // Now, see if we can extend the chain.
    // Look at u’s neighbors except x.
    int cnt = 0;
    int next = -1;
    for (int w : adj[u]) {
        if (w == x) continue;
        cnt++;
        next = w;
    }
    // If there is exactly one neighbor (i.e. the branch is a chain) then extend.
    if (cnt == 1) {
        vector<int> rest = getChain(u, next);
        chain.insert(chain.end(), rest.begin(), rest.end());
    }
    memo[key] = chain;
    return chain;
}
 
// --- MAIN ---
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> N;
    // Read the tree
    adj.assign(N+1, vector<int>());
    for (int i=1; i<=N-1; i++){
        int A, B; 
        cin >> A >> B;
        adj[A].push_back(B);
        adj[B].push_back(A);
    }
    cin >> M;
    // Read the speciality produced at each city.
    // (Cities are numbered 1..N.)
    speciality.resize(N+1);
    for (int i=1; i<=N; i++){
        cin >> speciality[i];
    }
 
    // ans[x] will store the answer for city x.
    vector<int> ans(N+1, 0);
 
    // Process each city x.
    // For city x, the idea is:
    //   - For every neighbor u of x, compute L(x,u) = (length of the chain from x->u)
    //   - If x is a leaf (degree 1), then the unique branch is the only branch and unique distances are 1..L(x,u).
    //   - Otherwise, let L1 = maximum chain length among neighbors,
    //       and let L2 = the second maximum (or 0 if x has only one neighbor).
    //     Then if the maximum L1 is unique (i.e. only one neighbor attains L1) the unique distances are
    //     d = L2+1, L2+2, …, L1.
    //   - Finally, “read off” the cities at these distances from the chain that gave L1 and count distinct specialities.
    for (int x = 1; x <= N; x++){
        int deg = adj[x].size();
        if(deg == 0) { // should not happen in a connected tree
            ans[x] = 0;
            continue;
        }
        // branchInfo: for each neighbor u of x, store pair {chain length, neighbor u}
        vector<pair<int,int>> branchInfo;
        for (int u : adj[x]){
            vector<int> chain = getChain(x, u);
            int len = chain.size(); // note: len is the maximum distance from x along branch u
            branchInfo.push_back({len, u});
        }
 
        if(deg == 1){
            // Only one branch. Then unique distances are 1..L, where L = chain length.
            int L1 = branchInfo[0].first;
            vector<int> chain = getChain(x, branchInfo[0].second);
            unordered_set<int> specSet;
            // d=1 corresponds to chain[0], d=2 to chain[1], …, d=L1 to chain[L1-1].
            for (int d = 1; d <= L1; d++){
                specSet.insert(speciality[ chain[d-1] ]);
            }
            ans[x] = specSet.size();
        } else {
            // x has at least two neighbors.
            int L1 = -1, L2 = -1;
            int countMax = 0; // count how many branches attain the maximum length L1.
            int bestNeighbor = -1;
            for (auto &p : branchInfo){
                int L = p.first;
                if(L > L1){
                    L2 = L1;
                    L1 = L;
                    bestNeighbor = p.second;
                    countMax = 1;
                } else if(L == L1){
                    countMax++;
                } else if(L > L2){
                    L2 = L;
                }
            }
            // If the maximum chain length appears at least twice then no distance d has S_x(d)==1.
            if(countMax != 1){
                ans[x] = 0;
            } else {
                // Unique distances for x are d = L2+1, L2+2, …, L1.
                vector<int> chain = getChain(x, bestNeighbor);
                unordered_set<int> specSet;
                // d (1-indexed) means chain index (d-1).
                for (int d = L2+1; d <= L1; d++){
                    specSet.insert(speciality[ chain[d-1] ]);
                }
                ans[x] = specSet.size();
            }
        }
    }
 
    // Output the answer for each city.
    for (int i=1; i<=N; i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32