Submission #1071505

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071505		Ignut	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	146 ms	22356 KiB

supertrees

// Ignut

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int P = 5;
const int MOD = 1e9 + 9;

int add(int a, int b) {
    return a + b >= MOD ? a + b - MOD : a + b;
}

int mult(int a, int b) {
    return 1ll * a * b % MOD;
}

// ===================================================================== //

void build(vector<vector<int>> b);

struct DSU {
    vector<int> p;
    vector<vector<int>> comp;
    void Init(int n) {
        p.clear(), comp.clear();
        for (int i = 0; i < n; i ++) p.push_back(i), comp.push_back({i});
    }
    int Get(int v) {
        return p[v] == v ? v : p[v] = Get(p[v]);
    }
    void Unite(int u, int v) {
        u = Get(u), v = Get(v);
        if (u == v) return;
        if (comp[u].size() > comp[v].size()) swap(u, v);
        p[u] = v;
        for (int val : comp[u]) comp[v].push_back(val);
    }
};

int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> b(n);
    for (int i = 0; i < n; i ++) b[i].assign(n, 0);
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (p[i][j] == 3)
                return 0;
        }
    }

    // ================= chains =========================== //

    bool have1[n] = {};
    int h[n];
    for (int i = 0; i < n; i ++) {
        int hsh = 0;
        int ppow = 1;
        for (int j = 0; j < n; j ++) {
            ppow = mult(ppow, P);
            hsh = add(hsh, mult(ppow, p[i][j]));
            have1[i] |= p[i][j] == 1;
        }
        h[i] = hsh;
    }
    DSU chains; chains.Init(n);
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (h[i] == h[j] && have1[i])
                chains.Unite(i, j);
        }
    }
    map<int, int> chain;
    int nextChain = 1;
    for (int i = 0; i < n; i ++) {
        if (chains.Get(i) != i) continue;
        if (chains.comp[i].size() == 1) continue;
        for (int v : chains.comp[i]) chain[v] = nextChain;
        nextChain ++;
        for (int j = 0; j + 1 < chains.comp[i].size(); j ++) {
            int u = chains.comp[i][j];
            int v = chains.comp[i][j + 1];
            b[u][v] = b[v][u] = true;
        }
    }

    // ================== cycles ========================== //

    DSU dsu; dsu.Init(n);
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            if (p[i][j] > 0) {
                dsu.Unite(i, j);
            }
        }
    }
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            bool f1 = (p[i][j] > 0);
            bool f2 = (dsu.Get(i) == dsu.Get(j));
            if (f1 != f2)
                return 0;
        }
    }

    for (int i = 0; i < n; i ++) {
        if (dsu.Get(i) != i) continue;
        // if (dsu.comp[i].size() == 1) continue;
        // if (dsu.comp[i].size() <= 2)
        //     return 0;
        // // cerr << dsu.comp[i].size() << '\n';
        // for (int j = 0; j < dsu.comp[i].size(); j ++) {
        //     int u = dsu.comp[i][j], v = dsu.comp[i][(j + 1) % dsu.comp[i].size()];
        //     b[u][v] = b[v][u] = 1;
        // }
        map<int, int> usedChain;
        vector<int> comp;
        for (int v : dsu.comp[i]) {
            if (!chain.count(v)) {
                comp.push_back(v);
                continue;
            }
            int ch = chain[v];
            if (usedChain.count(ch)) {
                continue;
            }
            usedChain[ch] ++;
            comp.push_back(v);
        }

        if (comp.size() == 1)
            continue;
        if (comp.size() == 2)
            return 0;
        
        for (int j = 0; j < comp.size(); j ++) {
            int u = comp[j];
            int v = comp[(j + 1) % comp.size()];
            b[u][v] = b[v][u] = true;
        }
    }

    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:81:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int j = 0; j + 1 < chains.comp[i].size(); j ++) {
      |                         ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int j = 0; j < comp.size(); j ++) {
      |                         ~~^~~~~~~~~~~~~

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