Submission #1146189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146189		madamadam3	Izlet (COI19_izlet)	C++20	0 / 100	2094 ms	36276 KiB

izlet

#include <bits/stdc++.h>
using namespace std;
 
// We'll use 0-indexing for nodes.
 
// Global variables
int N;
vector<vector<int>> fmat; // fmat[i][j] = number of distinct colors on path i<->j

// ********** Union–Find for 1‐comps **********
vector<int> uf_parent;
 
int uf_find(int a) {
    if(uf_parent[a] == a) return a;
    return uf_parent[a] = uf_find(uf_parent[a]);
}
 
void uf_union(int a, int b) {
    a = uf_find(a); b = uf_find(b);
    if(a == b) return;
    uf_parent[b] = a;
}
 
// ********** Global data for tree reconstruction **********
// We will store the final tree (which will have exactly N-1 edges)
vector<pair<int,int>> treeEdges; // each edge is (u,v), 0-indexed

// The final tree will be stored as an adjacency list:
vector<vector<int>> treeAdj;
 
// ********** LCA preprocessing **********
vector<int> par, depth;
 
void dfsTree(int u, int p) {
    par[u] = p;
    for (int v : treeAdj[u]) {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        dfsTree(v, u);
    }
}
 
// Simple LCA (O(n) per query, which is acceptable for N<=3000)
int getLCA(int u, int v) {
    while(depth[u] > depth[v]) u = par[u];
    while(depth[v] > depth[u]) v = par[v];
    while(u != v) {
        u = par[u];
        v = par[v];
    }
    return u;
}
 
// Returns the number of distinct colors on the unique path between u and v in the final tree.
// Uses the global "colors" vector.
int getDistinctOnPath(int u, int v, const vector<int>& colors) {
    int l = getLCA(u,v);
    vector<bool> seen(N+1, false);
    int cnt = 0;
    // Walk from u up to (but not including) l
    int cur = u;
    while(cur != l) {
        if (!seen[colors[cur]]) { seen[colors[cur]] = true; cnt++; }
        cur = par[cur];
    }
    // Walk from v up to (but not including) l
    cur = v;
    while(cur != l) {
        if (!seen[colors[cur]]) { seen[colors[cur]] = true; cnt++; }
        cur = par[cur];
    }
    // Count the LCA once
    if (!seen[colors[l]]) { cnt++; }
    return cnt;
}
 
// ********** DFS to assign colors **********
// colors[u] will hold the color assigned to node u (from 1 to N)
vector<int> colors;
// "coloredList" will store all nodes that have already been assigned a color.
vector<int> coloredList;
 
// Recursive DFS that “colors” the tree so that for every already–colored node w, 
// the distinct colors on the path from w to u equals fmat[w][u].
void dfsColor(int u, int p) {
    // For each child v, decide its color
    for (int v : treeAdj[u]) {
        if (v == p) continue;
 
        // Try candidate colors from 1 to N.
        for (int cand = 1; cand <= N; cand++) {
            // We must have: if edge (u,v) is between different 1–comps, then f(u,v)==2,
            // so in our tree adjacent nodes must have different colors.
            if (cand == colors[u]) continue;
 
            colors[v] = cand;
 
            bool ok = true;
            // Check the condition for every already colored node (other than v itself)
            for (int w : coloredList) {
                int cnt = getDistinctOnPath(w, v, colors);
                if (cnt != fmat[w][v]) {
                    ok = false;
                    break;
                }
            }
            if (ok) break;
        }
        coloredList.push_back(v);
        dfsColor(v, u);
    }
}
 
// ********** Main function **********
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int subtask;
    cin >> subtask >> N;
    fmat.assign(N, vector<int>(N, 0));
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> fmat[i][j];
        }
    }
 
    // === Phase 1: Contract nodes that must be the same color (1‐comps) ===
    uf_parent.resize(N);
    for (int i = 0; i < N; i++) uf_parent[i] = i;
    for (int i = 0; i < N; i++){
        for (int j = i+1; j < N; j++){
            if (fmat[i][j] == 1) {
                uf_union(i,j);
            }
        }
    }
 
    // Identify for every node its representative (the unique 1–comp id)
    vector<int> repId(N, -1);
    for (int i = 0; i < N; i++){
        repId[i] = uf_find(i);
    }
 
    // For every non–representative, attach it immediately to its representative.
    // (We choose the representative to be the one with the smallest index in that comp.)
    vector<bool> isRep(N, false);
    for (int i = 0; i < N; i++){
        if (repId[i] == i) { isRep[i] = true; }
    }
    for (int i = 0; i < N; i++){
        if (!isRep[i]){
            // attach i to its rep
            treeEdges.push_back({ repId[i], i });
        }
    }
 
    // === Phase 2: Among the representatives, use edges with f==2 to “reconstruct” the contracted tree ===
    // Collect all representatives.
    vector<int> reps;
    for (int i = 0; i < N; i++){
        if (isRep[i]) reps.push_back(i);
    }
    // Build a graph among representatives using candidate edges (f==2)
    vector<vector<int>> repGraph(N);
    int R = reps.size();
    for (int i = 0; i < R; i++){
        for (int j = i+1; j < R; j++){
            int u = reps[i], v = reps[j];
            if (fmat[u][v] == 2) {
                repGraph[u].push_back(v);
                repGraph[v].push_back(u);
            }
        }
    }
    // Find a spanning tree on the representatives (which is guaranteed to exist)
    vector<bool> vis(N, false);
    queue<int>q;
    if (!reps.empty()){
        q.push(reps[0]);
        vis[reps[0]] = true;
    }
    while(!q.empty()){
        int u = q.front(); q.pop();
        for (int v : repGraph[u]){
            if (!vis[v]){
                vis[v] = true;
                q.push(v);
                treeEdges.push_back({ u, v });
            }
        }
    }
 
    // === Build the final tree’s adjacency list ===
    treeAdj.assign(N, vector<int>());
    for (auto &e : treeEdges) {
        int u = e.first, v = e.second;
        treeAdj[u].push_back(v);
        treeAdj[v].push_back(u);
    }
 
    // === Phase 3: Assign colors by a DFS (the “greedy‐check” procedure) ===
    colors.assign(N, 0);
    // We choose an arbitrary root – say, the smallest representative (or 0)
    int root = 0;
    colors[root] = 1;
    coloredList.push_back(root);
 
    // Precompute parent and depth for LCA queries.
    par.assign(N, -1);
    depth.assign(N, 0);
    dfsTree(root, -1);
 
    dfsColor(root, -1);
 
    // === Output the answer ===
    // First line: colors (convert back to 1-indexed if desired)
    for (int i = 0; i < N; i++){
        cout << colors[i] << (i+1==N? "\n" : " ");
    }
    // Next N-1 lines: tree edges (we output 1-indexed nodes)
    for (auto &e : treeEdges){
        cout << e.first+1 << " " << e.second+1 << "\n";
    }
 
    return 0;
}

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