Submission #1146187

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

izlet

#include <bits/stdc++.h>
using namespace std;
 
// DSU for grouping vertices that must have the same colour (their rows are identical)
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 (we use 0-indexing)
int N;
vector<vector<int>> mat;
 
// For the group–tree we store for each group an id, a representative vertex, and a list of member vertices.
struct Group {
    int rep;
    vector<int> verts;
    // f = "distance from the chosen root" (the number from mat[rep_root][rep])
    int f;
    int col; // colour assigned to this group
    int parent; // parent group id in the group tree (-1 for root)
    vector<int> children;
};
 
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. DSU – group together vertices that “must” have the same colour.
    DSU dsu(N);
    for (int i=0; i<N; i++){
        for (int j=i+1; j<N; j++){
            // In any valid solution the matrix entry is 1 exactly when the entire path is monochromatic.
            if(mat[i][j]==1){
                dsu.unite(i,j);
            }
        }
    }
 
    // 2. Build groups. Two vertices in the same group have identical rows.
    map<int, int> groupId; // dsu-root -> new 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; // take first vertex encountered as representative
            g.verts.push_back(i);
            g.parent = -1;
            g.f = 0;
            g.col = 0;
            groups.push_back(g);
        } else {
            groups[groupId[r]].verts.push_back(i);
        }
    }
    int M = groups.size();
 
    // 3. Choose the group that contains vertex 0 as the "root".
    int rootGroup = groupId[ dsu.find(0) ];
    groups[rootGroup].f = 1; // by definition
    // For every other group, we will “set” f = mat[0][rep] (using the fact that in any valid solution,
    // if you take the vertex from the root–group as reference, the number of distinct colours on the path
    // from the root to a vertex v equals mat[0][v]).
    for (int i=0; i<M; i++){
        if(i==rootGroup) continue;
        groups[i].f = mat[0][ groups[i].rep ];
    }
 
    // 4. For every group (other than the root) we pick as its parent any group U 
    // with f = f(child) - 1 such that mat[ U.rep ][ child.rep ] == 2.
    // (It is not hard to show that such a U exists.)
    for (int i=0; i<M; i++){
        if(i==rootGroup) continue;
        int ftarget = groups[i].f - 1;
        int parCandidate = -1;
        for (int j=0; j<M; j++){
            if(j==i) continue;
            if(groups[j].f == ftarget && mat[ groups[j].rep ][ groups[i].rep ] == 2) {
                parCandidate = j; break;
            }
        }
        // (In a correct instance, parCandidate will be found.)
        groups[i].parent = parCandidate;
        groups[parCandidate].children.push_back(i);
    }
 
    // 5. Now assign colours to groups by doing a DFS on the group–tree.
    // The idea is: on the unique path from the root group to any group G, the number of distinct colours must equal groups[G].f.
    // So if f(child)==f(parent) then we force the same colour;
    // if f(child)==f(parent)+1 then we assign a colour new (i.e. not used on the path).
    vector<int> groupColor(M, 0);
    vector<int> curPath; // colours used on the current path
    function<void(int)> dfs = [&](int u) {
        // If u is the root, assign colour 1 arbitrarily.
        if(u==rootGroup) {
            groups[u].col = 1;
            curPath.push_back(1);
        }
        for (int v : groups[u].children) {
            // The desired distinct count on the path from the root to group v is groups[v].f.
            // The current distinct count on the path (from root to u) is (int)curPath.size().
            if(groups[v].f == (int)curPath.size() + 1){
                // must choose a new colour – choose the smallest colour from 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].f == (int)curPath.size()){
                // do not introduce a new colour: use parent's colour.
                groups[v].col = groups[u].col;
                curPath.push_back(groups[u].col);
                dfs(v);
                curPath.pop_back();
            } else {
                // If the number does not match, the instance is not “nice” – but the problem guarantees a solution.
                // (We could also try backtracking here.)
                groups[v].col = 1;
                curPath.push_back(1);
                dfs(v);
                curPath.pop_back();
            }
        }
    };
    dfs(rootGroup);
 
    // 6. Now “expand” the groups to form the final tree.
    // For each group, we join all vertices in that group arbitrarily (for example, in a chain).
    // Then, for every group (except the root) we add an edge connecting one vertex of the group
    // (say, its representative) to one vertex of its parent group.
    vector<pair<int,int>> ansEdges;
    // Within groups:
    for (int i=0; i<M; i++){
        auto &g = groups[i];
        if(g.verts.size() > 1){
            sort(g.verts.begin(), g.verts.end());
            for (int j=1; j<(int)g.verts.size(); j++){
                // use 1-indexed vertices in output
                ansEdges.push_back({ g.verts[j-1] + 1, g.verts[j] + 1 });
            }
        }
    }
    // Between groups (the spanning tree on groups):
    for (int i=0; i<M; i++){
        if(i==rootGroup) continue;
        int par = groups[i].parent;
        // connect group i and group par by taking (for example) the representative of each.
        ansEdges.push_back({ groups[i].rep + 1, groups[par].rep + 1 });
    }
 
    // 7. Now output a colouring for the N vertices.
    // Each vertex gets the colour 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:
    for (int i=0; i<N; i++){
        cout << ansColor[i] << (i==N-1? "\n" : " ");
    }
    for (auto &e : ansEdges){
        cout << e.first << " " << e.second << "\n";
    }
 
    return 0;
}

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