Submission #1241686

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241686		domi	Connecting Supertrees (IOI20_supertrees)	C++20	40 / 100	125 ms	24568 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

// #define int long long
// #define fi first
// #define se second
//
// #define sz(a) (int)((a).size())
// #define all(a) (a).begin(), (a).end()
//
// #define lsb(x) (x & (-x))
// #define vi vector<int>
// #define YES { cout << "YES" << endl; return; }
// #define NO { cout << "NO" << endl; return; }
//
// using ll = long long;
// using pii = std::pair<int, int>;

const int NMAX = 1e5;

using namespace std;

struct DSU {
    vector<int> data;
    DSU(int N) : data(N, -1) {}

    int find(int k) { return data[k] < 0 ? k : data[k] = find(data[k]); }

    int unite(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        return true;
    }

    template<typename F>
    int unite(int x, int y,const F &f) {
        if ((x = find(x)) == (y = find(y))) return false;
        if (data[x] > data[y]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
        f(x, y);
        return true;
    }

    int size(int k) { return -data[find(k)]; }

    int same(int x, int y) { return find(x) == find(y); }
};

vector<int>L[NMAX + 5];


int construct(vector<vector<int>> D) {
    int n = D.size();
    vector<vector<int>>sol(n, vector<int>(n, 0));
    unique_ptr<DSU[]> ds(new DSU[3]{DSU(n), DSU(n), DSU(n)});

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (D[i][j] == 3)
                return 0;
            ds[D[i][j]].unite(i, j);
        }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if ((ds[1].same(i, j) && D[i][j] != 1) || (ds[2].same(i, j) && D[i][j] != 2))
                return 0;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (ds[1].find(i) == i)
            L[ds[2].find(i)].push_back(i);
        else {
            sol[i][ds[1].find(i)] = 1;
            sol[ds[1].find(i)][i] = 1;
        }
    }

    for (int i = 0; i < n; ++i) {
        if (L[i].size() < 2) continue;

        if (L[i].size() == 2) return 0;

        ///prima data il fac lant
        for (int j = 1; j < L[i].size(); ++j) {
            int cur = L[i][j];
            int prev = L[i][j - 1];

            sol[cur][prev] = 1;
            sol[prev][cur] = 1;
        }

        ///conectez ultimul element din lant cu primul ca sa se formeze ciclu
        int first = L[i][0];
        int last = L[i][L[i].size() - 1];

        sol[first][last] = 1;
        sol[last][first] = 1;
    }

    build(sol);
    return 1;
}


// signed main() {
//     cin.tie(nullptr)->sync_with_stdio(false);
//
//     return 0;
// }

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