p449.ans1
======================
1
2
3

=================
p449.ans2
======================
1
2
3
5
4

=================
p449.ans3
======================
1
4
2
3

=================
p449.ans4
======================
1
4
2
3

=================
p449.ans5
======================
1
2
3
4

=================
p449.ans6
======================
1
4
2
3

=================
p449.ans7
======================
1
2
3

=================
p449.ans8
======================
1

=================
p449.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m, q;
vector<pair<int, vector<int>>> lines;
vector<int> queries;

void read() {
    cin >> n >> m >> q;
    lines.resize(m);
    for(auto& [y, members]: lines) {
        int len;
        cin >> y >> len;
        members.resize(len);
        cin >> members;
    }
    queries.resize(q);
    cin >> queries;
}

void solve() {
    // Each horizontal line is an internal node whose children are the
    // subgroups it joins, leaves 1..n are leaf nodes. A larger Y sits lower in
    // the picture (more similar), so it is a deeper merge; processing lines by
    // decreasing Y and unioning each line's members lets a DSU map every member
    // id to the current top node of its group, and a fresh internal node for
    // the line collects those tops as children. What is left when M < N - 1 is
    // a forest of such trees plus untouched leaves.
    //
    // A clean diagram means every subtree occupies a contiguous block, so the
    // only freedom is the left-to-right order of each node's children, chosen
    // for the lexicographically smallest leaf sequence. The lex-smallest
    // arrangement of a subtree always begins with that subtree's minimum leaf
    // (the child holding the min sorts first, by induction). Sibling subtrees
    // have disjoint leaves, so two sibling sequences already differ at their
    // first element: ordering children by their full sequence is identical to
    // ordering them by their subtree minimum. So we sort children (and the
    // forest roots) by subtree min and read the leaves off in a pre-order walk.
    //
    // Internal nodes get ids n+1.. in creation order, and every child has a
    // smaller id than its parent, so subtree mins fill in by a single sweep in
    // increasing id. The final walk and the DSU find are iterative to stay safe
    // on chains of depth up to n.

    sort(lines.begin(), lines.end(), [](const auto& a, const auto& b) {
        return a.first > b.first;
    });

    int total = n + m;
    vector<int> par(n + 1);
    vector<int> node_of(n + 1);
    for(int i = 1; i <= n; i++) {
        par[i] = i;
        node_of[i] = i;
    }

    auto find = [&](int x) {
        while(par[x] != x) {
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    };

    vector<vector<int>> children(total + 1);
    int next_id = n;
    for(const auto& [y, members]: lines) {
        int cur = ++next_id;
        int base = find(members[0]);
        for(int v: members) {
            int r = find(v);
            children[cur].push_back(node_of[r]);
            par[r] = base;
        }

        base = find(base);
        node_of[base] = cur;
    }

    vector<int> subtree_min(total + 1);
    for(int i = 1; i <= n; i++) {
        subtree_min[i] = i;
    }
    for(int id = n + 1; id <= total; id++) {
        int best = INT_MAX;
        for(int c: children[id]) {
            best = min(best, subtree_min[c]);
        }

        subtree_min[id] = best;
    }

    auto by_min = [&](int a, int b) { return subtree_min[a] < subtree_min[b]; };
    for(int id = n + 1; id <= total; id++) {
        sort(children[id].begin(), children[id].end(), by_min);
    }

    vector<int> roots;
    for(int i = 1; i <= n; i++) {
        if(find(i) == i) {
            roots.push_back(node_of[i]);
        }
    }

    sort(roots.begin(), roots.end(), by_min);

    vector<int> order;
    order.reserve(n);
    vector<int> stack;
    for(auto it = roots.rbegin(); it != roots.rend(); ++it) {
        stack.push_back(*it);
    }

    while(!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        if(u <= n) {
            order.push_back(u);
            continue;
        }

        const auto& ch = children[u];
        for(auto it = ch.rbegin(); it != ch.rend(); ++it) {
            stack.push_back(*it);
        }
    }

    for(int pos: queries) {
        cout << order[pos - 1] << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
p449.in1
======================
3 2 3
10 2 1 2
20 2 3 2
1
2
3

=================
p449.in2
======================
5 2 5
10 3 1 2 4
20 3 2 3 5
1
2
3
4
5

=================
p449.in3
======================
4 1 4
10 2 1 4
1
2
3
4

=================
p449.in4
======================
4 3 4
30 2 1 4
20 2 2 4
10 2 3 4
1
2
3
4

=================
p449.in5
======================
4 3 4
10 2 1 4
20 2 2 4
30 2 3 4
1
2
3
4

=================
p449.in6
======================
4 3 4
10 2 1 2
15 2 1 4
20 2 2 3
1
2
3
4

=================
p449.in7
======================
3 2 3
10 2 2 3
20 2 1 2
1
2
3

=================
p449.in8
======================
1 0 1
1

=================
statement.txt
======================
449. Dendrograms
Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Nod Ishimatsu is a student majoring computer science. He has wrote a program that performs hierarchical clustering, for the end-term project in a class of Introduction to Artificial Intellegence. Clustering is the process of grouping a set of objects into subsets called clusters, so that each cluster contains those similar in some sense. Hierarchical clustering is a way to do this indirectly; it produces trees (or in this problem collections of trees) called dendrograms. A dendrogram represents similarity among objects. The figure below shows an example dendrogram.


Leaves (at the bottom) denote objects. The horizontal lines split the objects into two or more subgroups and indicate objects in different subgroups are less similar than those in the same subgroup. Thus, basically, the upper the line is located, the less similar the objects or the sets of objects connected by it. We can have, for example, three clusters by using the top two horizontal lines. Nod's program also outputs dendrograms, but it has two problems. Firstly, output dendrograms are sometimes not fully connected, i.e. output can contain multiple trees. We don't deal with this problem here. Secondly, the produced dendrograms are fairly messy. Here is an example:


Maybe we want to change the order of the objects and have a clean diagram like the one shown above. Your task is to write a program for this purpose, i.e. reordering the objects for a clean diagram. Here, by clean diagrams, we mean those with no crosses of vertical and horizontal lines. There is usually more than one clean diagram; among them your program should pick the one in which the object of the smaller number comes to the left (in a lexicographical manner). Refer to the sections of Input and Output for the detailed specification.
Input
The input is given in the following format:
N M Q
splitInfo1
splitInfo2
...
splitInfoM
query1
query2
...
queryQ
The first line contains three integers N (1 ≤ N ≤ 100000), M (0 ≤ M < N), and Q (1 ≤ Q ≤ 1000, Q ≤ N), which represents the numbers of objects, horizontal lines, and queries respectively. Then M lines follow to describe horizontal lines. Each line is given in the following format: Y L V1 V2... VL Y (0 ≤ Y ≤ 109) denotes the vertical position of the horizontal line; the smaller value indicates the upper position (or the less similarity). L is the number of vertical lines (i.e. objects or subgroups of objects) connected by the line. Vi (for 1 ≤ i ≤ L) indicates each of the vertical lines. Each object is indicated by its identifier, a unique number from 1 to N. Each subgroup of objects is indicated by the identifier of an arbitrary object in the subgroup. Following the description of horizontal lines, there are Q lines each of which indicates a leaf index at which your program should report which object should be placed. The index is given by a number from 1 (leftmost) to N (rightmost).
Output
Print Q lines where the i-th line indicates the identifier of the object at the i-th queried position.
Example(s)
sample input
sample output
3 2 3
10 2 1 2
20 2 3 2
1
2
3
1
2
3

sample input
sample output
5 2 5
10 3 1 2 4
20 3 2 3 5
1
2
3
4
5
1
2
3
5
4

sample input
sample output
4 1 4
10 2 1 4
1
2
3
4
1
4
2
3

sample input
sample output
4 3 4
30 2 1 4
20 2 2 4
10 2 3 4
1
2
3
4
1
4
2
3

sample input
sample output
4 3 4
10 2 1 4
20 2 2 4
30 2 3 4
1
2
3
4
1
2
3
4

sample input
sample output
4 3 4
10 2 1 2
15 2 1 4
20 2 2 3
1
2
3
4
1
4
2
3

sample input
sample output
3 2 3
10 2 2 3
20 2 1 2
1
2
3
1
2
3

sample input
sample output
1 0 1
1
1

=================
