Submission #703846

#	Time	Username	Problem	Language	Result	Execution time	Memory
703846		bebra	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	250 ms	22156 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


struct DSU {
    vector<int> parent;
    vector<int> size;

    DSU(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        size.assign(n, 1);
    }

    int find(int v) {
        if (parent[v] == v) {
            return v;
        } else {
            return parent[v] = find(parent[v]);
        }
    }

    void unite(int u, int v) {
        if (u == v) return;
        u = find(u);
        v = find(v);
        if (size[u] > size[v]) swap(u, v);
        parent[u] = v;
        size[v] += size[u];
    }
};


int construct(vector<vector<int>> p) {
	int n = p.size();

	vector<vector<int>> g(n, vector<int>(n));

    // 1) must be transitive:
    // p[u][w] * p[w][v] = p[v][w] * p[w][u] = p[u][v] = p[v][u], for any u, v, w
    bool ok = true;
    DSU dsu(n);
    for (int u = 0; u < n; ++u) {
        for (int v = u + 1; v < n; ++v) {
            if (p[u][v] > 0) {
                dsu.unite(u, v);
            }
        }
    }

    map<int, vector<int>> comps;
    for (int v = 0; v < n; ++v) {
        comps[dsu.find(v)].push_back(v);
    }
    
    for (const auto& [c, comp] : comps) {
        int m = comp.size();
        if (m == 1) continue;

        map<int, int> color;
        for (int i = 0; i < m; ++i) {
            int u = comp[i];
            for (int j = 0; j < m; ++j) {
                if (i == j) continue;
                
                int v = comp[j];
                
                if (u == v) continue;
                
                if (p[u][v] == 0) {
                    ok = false;
                }

                if (p[u][v] == 1) {
                    color[u] = 1;
                    color[v] = 1;
                }

                if (p[u][v] == 2) {
                    if (color[u] != 1) {
                        color[u] = 2;
                    }
                    if (color[v] != 1) {
                        color[v] = 2;
                    }
                }
            }
        }

        vector<int> line;
        int cnt1 = 0;
        for (const auto& [v, col] : color) {
            if (col == 1) {
                ++cnt1;
                line.push_back(v);
            }
        }
        int cnt2 = 0;
        for (const auto& [v, col] : color) {
            if (col == 2) {
                ++cnt2;
                line.push_back(v);
            }
        }
        if (cnt1 == 0 && cnt2 == 2) {
            ok = false;
            break;
        }
        if (cnt1 > 0 && cnt2 == 1) {
            ok = false;
            break;
        }
        // if (cnt1 + cnt2 != m) {
            // ok = false;
            // break;
        // }
        
        for (int i = 0; i < m - 1; ++i) {
            g[line[i]][line[i + 1]] = 1;
            g[line[i + 1]][line[i]] = 1;
        }
        
        if (cnt2 > 1) {
            g[line[cnt1 - 1]][line.back()] = g[line.back()][line[cnt1 - 1]] = 1;
        }

    }


    // dbg(ok);
    // for (int i = 0; i < n; ++i) {
    //     for (int j = 0; j < n; ++j) {
    //         if (g[i][j] == 1) {
    //             cout << i + 1 << ' ' << j + 1 << '\n';
    //         }
    //     }
    //     cout << '\n';
    // }
	if (ok) {
        build(g);
        return 1;
    }
    return 0;
}

// int main() {
//     int n;
//     cin >> n;
//     vector<vector<int>> p(n, vector<int>(n));
//     for (int i = 0; i < n; ++i) {
//         for (int j = 0; j < n; ++j) {
//             cin >> p[i][j];
//         }
//     }
//     construct(p);

// }

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4