Submission #427328

#	Time	Username	Problem	Language	Result	Execution time	Memory
427328		magmag	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	254 ms	24004 KiB

supertrees

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

struct UF {
    vi p, rnk;
    int nsets;

    UF(int n) {
        p = vi(n);
        for (int i = 0; i < n; ++i)p[i] = i;
        rnk = vi(n);
        nsets = n;
    }

    int parent(int i) {
        if (p[i] == i)return i;
        return p[i] = parent(p[i]);
    }
     
    bool check(int a, int b) {
        return parent(a) == parent(b);
    }
     
    void join(int a, int b) {
        if (check(a,b))return;
        nsets--;
     
        a = parent(a);
        b = parent(b);
     
        if (rnk[a] > rnk[b]) {
            p[b] = a;
        } else {
            p[b] = a;
            if (rnk[a] == rnk[b]) {
                rnk[b]++;
            }
        }
    }
};

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

    UF uf(n);
 
    vector<vi> ans(n, vi(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)continue;
            if (p[i][j]) {
                uf.join(i,j);
            } else {
                if (uf.check(i,j))return 0;
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        int par = uf.parent(i);
        if (par == i)continue;
        ans[i][par] = 1;
        ans[par][i] = 1;
    }
 
    build(ans);
    return 1;
}

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