Submission #807883

#	Time	Username	Problem	Language	Result	Execution time	Memory
807883		drdilyor	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	167 ms	24008 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
using ll = long long;
const int inf = 1e9;

#define debug(args...) cout << "[" << #args << "]: "; debug_out(args...);
void debug_out() {
    cout << endl;
}
template<typename H, typename... T>
void debug_out(H h, T... t) {
    cout << h << ", ";
    debug_out(t...);
}

struct DSU {
    int n;
    vector<int> par;
    DSU(int n) : n(n), par(n) {
        for (int i = 0; i < n; i++)
            par[i] = i;
    }
    void merge(int a, int b) {
        par[get(b)] = get(a);
    }
    int get(int i) {
        return par[i] == i ? i : par[i] = get(par[i]);
    }
};

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
    DSU cc(n);
    vector ans(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j]) cc.merge(i, j);
        }
    }
    for (int i = 0; i< n; i++)
        for (int j =0; j < n; j++)
            if (p[i][j] != (cc.get(i) == cc.get(j)))
                return 0;

    vector<vector<int>> full(n);
    for (int i = 0; i < n; i++)
        full[cc.get(i)].push_back(i);
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < (int)full[i].size(); j++) {
            ans[full[i][j]][full[i][j-1]] =
                ans[full[i][j-1]][full[i][j]] = 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