Submission #1215740

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215740		madamadam3	Network (BOI15_net)	C++20	0 / 100	0 ms	324 KiB

net

/**********************************************************************
*  Read a 1-indexed tree, find a centroid, root there,                *
*  hash the tree “( … child-hashes … )” style (lexicographically      *
*  sorting the hashes), then perform a second DFS that always visits  *
*  the child with the smallest hash first.  The second DFS records    *
*  tin / tout / depth arrays and collects all leaves in the order     *
*  they are first encountered.                                        *
**********************************************************************/
#include <bits/stdc++.h>
using namespace std;

struct TreeHasher {
    int n;                                // number of vertices
    vector<vector<int>> g;                // 1-indexed adjacency list
    vector<int> sz;                       // subtree sizes
    int centroid;                         // chosen centroid
    vector<string> h;                     // hash of subtree rooted at v
    vector<int> tin, tout, depth;         // euler timestamps & depths
    vector<int> eulerLeaves;              // leaves in visit order
    int timer = 0;

    explicit TreeHasher(int N) : n(N) {
        g.assign(n + 1, {});
        sz.assign(n + 1, 0);
        h.assign(n + 1, "");
        tin.assign(n + 1, 0);
        tout.assign(n + 1, 0);
        depth.assign(n + 1, 0);
    }

    /*----------------------------------------------------------------*/
    /* 1. centroid (classic single pass)                               */
    /*----------------------------------------------------------------*/
    void dfsSz(int u, int p) {
        sz[u] = 1;
        bool isCentroid = true;
        for (int v : g[u])
            if (v != p) {
                dfsSz(v, u);
                sz[u] += sz[v];
                if (sz[v] * 2 > n) isCentroid = false;
            }
        if ((n - sz[u]) * 2 > n) isCentroid = false;
        if (isCentroid) centroid = u;
    }

    /*----------------------------------------------------------------*/
    /* 2. subtree hash (“canonical form” of unordered rooted tree)     */
    /*----------------------------------------------------------------*/
    string dfsHash(int u, int p) {
        vector<string> childHashes;
        for (int v : g[u])
            if (v != p) childHashes.push_back(dfsHash(v, u));

        sort(childHashes.begin(), childHashes.end());
        string cur = "(";
        for (auto& s : childHashes) cur += s;
        cur += ")";
        return h[u] = cur;
    }

    /*----------------------------------------------------------------*/
    /* 3. stable-order DFS: children visited in ascending hash order   */
    /*----------------------------------------------------------------*/
    void dfsOrder(int u, int p) {
        tin[u] = ++timer;
        bool isLeaf = (u != centroid && g[u].size() == 1);
        if (isLeaf) eulerLeaves.push_back(u);

        // collect & sort children by their already-computed hashes
        vector<int> children;
        for (int v : g[u]) if (v != p) children.push_back(v);
        sort(children.begin(), children.end(),
             [&](int a, int b) { return h[a] < h[b]; });

        for (int v : children) {
            depth[v] = depth[u] + 1;
            dfsOrder(v, u);
        }
        tout[u] = ++timer;
    }

    /*----------------------------------------------------------------*/
    /* Main entry point                                               */
    /*----------------------------------------------------------------*/
    void process() {
        dfsSz(1, 0);                     // pick centroid
        dfsHash(centroid, 0);            // hashes with centroid as root
        depth[centroid] = 0;
        dfsOrder(centroid, 0);           // stable-order DFS
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    TreeHasher TH(n);

    for (int i = 0, u, v; i < n - 1; ++i) {
        cin >> u >> v;
        // u++; v++;
        TH.g[u].push_back(v);
        TH.g[v].push_back(u);
    }

    TH.process();

    /*-------------------------------------------------------------*/
    /*  Example output – adjust / remove as you need               */
    /*-------------------------------------------------------------*/
    // cout << "Centroid: " << TH.centroid << '\n';
    // cout << "Global hash: " << TH.h[TH.centroid] << '\n';

//     cout << "tin:";
//     for (int i = 1; i <= n; ++i) cout << ' ' << TH.tin[i];
//     cout << "\ntout:";
//     for (int i = 1; i <= n; ++i) cout << ' ' << TH.tout[i];
//     cout << "\ndepth:";
//     for (int i = 1; i <= n; ++i) cout << ' ' << TH.depth[i];
//     cout << '\n';

//     cout << "Leaves in visit order:";
//     for (int v : TH.eulerLeaves) cout << ' ' << v;
//     cout << '\n';

    deque<int> dd(TH.eulerLeaves.begin(), TH.eulerLeaves.end());
    cout << ((TH.eulerLeaves.size() + 1) / 2) << "\n";
    cout << dd.front() << " " << dd.back() << "\n";
    dd.pop_back(); dd.pop_front();

    while (!dd.empty()) {
        int c1 = dd.front(); dd.pop_front();
        int c2 = dd.front(); dd.pop_front();

        cout << c1 << " " << c2 << "\n";
        if (dd.size() == 1) {
            int c3 = dd.front(); dd.pop_front();
            cout << c2 << " " << c3 << "\n";
        }
    }
}

• Subtask 1: 0 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37