Submission #1146186

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146186		madamadam3	Izlet (COI19_izlet)	C++20	18 / 100	265 ms	36156 KiB

izlet

#include <bits/stdc++.h>
using namespace std;
 
// DSU for grouping vertices that must have the same color – that is, forming a 1–comp.
struct DSU {
    vector<int> par;
    DSU(int n) : par(n) {
        for (int i = 0; i < n; i++) par[i] = i;
    }
    int find(int a) {
        return par[a] == a ? a : par[a] = find(par[a]);
    }
    void unite(int a, int b) {
        a = find(a); b = find(b);
        if(a != b) par[b] = a;
    }
};
 
// Global variables (using 0-indexing)
int N;
vector<vector<int>> mat;
 
// Each group represents a maximal 1–comp (i.e. a set of vertices that are all connected by f(u,v)=1)
// After contraction, every two vertices from different groups have f(u,v) ≥ 2.
struct Group {
    int rep;              // one chosen representative vertex
    vector<int> verts;    // all vertices in the 1–comp
    int level;            // the “level” = f(root, rep) (should equal the number of distinct colors on the path from the root)
    int col;              // color assigned to this group (all its vertices get this color)
    int parent;           // parent group in the contracted tree (–1 for the root group)
    vector<int> children; // children groups
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int subtask;
    cin >> subtask >> N;
    mat.assign(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> mat[i][j];
        }
    }
 
    // 1. Collapse vertices that must be the same color (i.e. f(u,v)=1) into 1–comps.
    DSU dsu(N);
    for (int i = 0; i < N; i++){
        for (int j = i+1; j < N; j++){
            if(mat[i][j] == 1)
                dsu.unite(i, j);
        }
    }
 
    // 2. Build the list of groups (1–comps). By the problem’s consistency,
    // all vertices in one 1–comp have identical rows and must get the same color.
    map<int, int> groupId; // maps DSU root -> group id
    vector<Group> groups;
    for (int i = 0; i < N; i++){
        int r = dsu.find(i);
        if(groupId.find(r) == groupId.end()){
            groupId[r] = groups.size();
            Group g;
            g.rep = i; // choose the first encountered vertex as representative
            g.verts.push_back(i);
            g.parent = -1;
            g.level = 0;
            g.col = 0;
            groups.push_back(g);
        } else {
            groups[groupId[r]].verts.push_back(i);
        }
    }
    int M = groups.size();
 
    // 3. Choose the 1–comp that contains vertex 0 as the root.
    int rootGroup = groupId[ dsu.find(0) ];
    groups[rootGroup].level = 1; // by definition, the path from the root to itself has 1 distinct color.
    // For every other group, define its level as mat[0][rep].
    for (int i = 0; i < M; i++){
        if(i == rootGroup) continue;
        groups[i].level = mat[0][ groups[i].rep ];
    }
 
    // 4. Connect the groups. In a valid tree, when moving from a vertex to its neighbor
    // (from a group to another), the number of distinct colors increases exactly by one.
    // So for every group (other than the root), we choose as its parent any group U
    // with level = (child’s level - 1) and such that f(U.rep, child.rep) = 2.
    for (int i = 0; i < M; i++){
        if(i == rootGroup) continue;
        int targetLevel = groups[i].level - 1;
        int parCandidate = -1;
        for (int j = 0; j < M; j++){
            if(j == i) continue;
            if(groups[j].level == targetLevel && mat[ groups[j].rep ][ groups[i].rep ] == 2) {
                parCandidate = j; 
                break;
            }
        }
        // In a correct instance such a candidate always exists.
        groups[i].parent = parCandidate;
        groups[parCandidate].children.push_back(i);
    }
 
    // 5. Now assign colors to groups by doing a DFS on the contracted (group) tree.
    // The idea: along the path from the root, the number of distinct colors must equal the level.
    // When moving from a group to a child, if the child's level equals (current distinct count + 1),
    // then we must pick a new color (one not already in the current path). Otherwise, if the level
    // does not increase, reuse the parent’s color.
    vector<int> curPath; // stores the colors on the current root-to-node path
    function<void(int)> dfs = [&](int u) {
        // For the root group we already assign an arbitrary color.
        if(u == rootGroup && curPath.empty()){
            groups[u].col = 1;
            curPath.push_back(1);
        }
        for (int v : groups[u].children) {
            if(groups[v].level == (int)curPath.size() + 1) {
                // Must introduce a new color. Choose the smallest color in {1,...,N} not in curPath.
                vector<bool> used(N+1, false);
                for (int c : curPath) used[c] = true;
                int newcol = 1;
                while(newcol <= N && used[newcol]) newcol++;
                groups[v].col = newcol;
                curPath.push_back(newcol);
                dfs(v);
                curPath.pop_back();
            } else if(groups[v].level == (int)curPath.size()){
                // Level remains the same: assign the same color as the parent.
                groups[v].col = groups[u].col;
                curPath.push_back(groups[u].col);
                dfs(v);
                curPath.pop_back();
            } else {
                // For a correct instance, this case should not occur.
                groups[v].col = 1;
                curPath.push_back(1);
                dfs(v);
                curPath.pop_back();
            }
        }
    };
    dfs(rootGroup);
 
    // 6. “Expand” the groups to form the final tree.
    // Inside each 1–comp we connect the vertices arbitrarily (here, in a chain),
    // and then connect each group to its parent by linking the representative vertices.
    vector<pair<int,int>> ansEdges;
    // Connect vertices inside the same 1–comp:
    for (int i = 0; i < M; i++){
        auto &g = groups[i];
        if(g.verts.size() > 1){
            sort(g.verts.begin(), g.verts.end());
            for (size_t j = 1; j < g.verts.size(); j++){
                ansEdges.push_back({ g.verts[j-1] + 1, g.verts[j] + 1 });
            }
        }
    }
    // Connect different groups (the spanning tree on 1–comps):
    for (int i = 0; i < M; i++){
        if(i == rootGroup) continue;
        int par = groups[i].parent;
        ansEdges.push_back({ groups[i].rep + 1, groups[par].rep + 1 });
    }
 
    // 7. Now assign each vertex the color of its group.
    vector<int> ansColor(N, 0);
    for (int i = 0; i < N; i++){
        int gr = groupId[ dsu.find(i) ];
        ansColor[i] = groups[gr].col;
    }
 
    // Output the vertex colors.
    for (int i = 0; i < N; i++){
        cout << ansColor[i] << (i == N-1 ? "\n" : " ");
    }
    // Output the tree edges.
    for (auto &e : ansEdges){
        cout << e.first << " " << e.second << "\n";
    }
 
    return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57