Submission #703910

#	Time	Username	Problem	Language	Result	Execution time	Memory
703910		bebra	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	175 ms	22188 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;
    int comps_n;
 
    DSU(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        size.assign(n, 1);
        comps_n = n;
    }
 
    int find(int v) {
        if (parent[v] == v) {
            return v;
        } else {
            return parent[v] = find(parent[v]);
        }
    }
 
    void unite(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        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));
 
    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);
            }
        }
    }
 
    auto add_edge = [&](int u, int v) {
        g[u][v] = g[v][u] = 1;
    };
 
    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;
 
        DSU curr_groups(m);
        vector<int> cycle;
        bool has_cycle = false;
        bool has_two = false;
        bool has_three = false;
        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;
                    break;
                }
                if (p[u][v] == 2) {
                    has_two = true;
                    has_cycle = true;
                }
                if (p[u][v] == 3) {
                    has_three = true;
                    has_cycle = true;
                }
                if (p[u][v] == 1) {
                    curr_groups.unite(i, j);
                }
            }
        }
        if (has_two && has_three) {
            ok = false;
            break;
        }
        if (!has_cycle) {
            for (int i = 0; i < m - 1; ++i) {
                add_edge(comp[i], comp[i + 1]);
            }
            continue;
        }
 
        map<int, vector<int>> groupsf;
        for (int i = 0; i < m; ++i) {
            if (curr_groups.size[curr_groups.find(i)] > 1) {
                groupsf[curr_groups.find(i)].push_back(comp[i]);
            } else {
                cycle.push_back(comp[i]);
            }
        }
 
        int groups_n = groupsf.size();
        vector<vector<int>> groups(groups_n);
        {
            int i = 0;
            for (const auto& [f, v] : groupsf) {
                groups[i] = v;
                ++i;
            }
        }
        
        for (int i = 0; i < groups_n; ++i) {
            int b = groups[i].size();
            for (int j = 0; j < b - 1; ++j) {
                add_edge(groups[i][j], groups[i][j + 1]);
            }
            for (auto u : groups[i]) {
                for (auto v : groups[i]) {
                    if (p[u][v] != 1) {
                        ok = false;
                        break;
                    }
                }

                for (int j = i + 1; j < groups_n; ++j) {
                    for (auto v : groups[j]) {
                        if (has_two && p[u][v] != 2) {
                            ok = false;
                            break;
                        }
                        if (has_three && p[u][v] != 3) {
                            ok = false;
                            break;
                        }
                    }
                }
            }
        }
 
        for (int i = 0; i < groups_n; ++i) {
            cycle.push_back(groups[i].back());
        }

        int cycle_size = cycle.size();
 
        if (has_two && cycle_size <= 2) {
            ok = false;
            break;
        }
        if (has_three && cycle_size <= 3) {
            ok = false;
            break;
        }

        for (int i = 0; i < cycle_size - 1; ++i) {
            add_edge(cycle[i], cycle[i + 1]);
        }
        add_edge(cycle[0], cycle.back());
        if (has_three) {
            add_edge(cycle[0], cycle[2]);
        }
    }
 
	if (ok) {
        build(g);
        return 1;
    }
    return 0;
}

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