Submission #1032891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1032891		Zicrus	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	142 ms	24324 KiB

supertrees

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

typedef long long ll;

vector<ll> lnk1, lnk2;

ll find1(ll a) {
    if (lnk1[a] != a) lnk1[a] = find1(lnk1[a]);
    return lnk1[a];
}

ll find2(ll a) {
    if (lnk2[a] != a) lnk2[a] = find2(lnk2[a]);
    return lnk2[a];
}

void unite1(ll a, ll b) {
    a = find1(a); b = find1(b);
    lnk1[b] = a;
}

void unite2(ll a, ll b) {
    a = find2(a); b = find2(b);
    lnk2[b] = a;
}

int construct(vector<vector<int>> p) {
    ll n = p.size();
    lnk1 = vector<ll>(p.size());
    lnk2 = vector<ll>(p.size());
    for (int i = 0; i < n; i++) lnk1[i] = lnk2[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (p[i][j] == 3) return 0;
            if (p[i][j] == 2) unite2(i, j);
            if (p[i][j] == 1) unite1(i, j);
        }
    }

    vector<set<ll>> clubs1(n), clubs2(n);
    for (int i = 0; i < n; i++) {
        clubs1[find1(i)].insert(i);
        clubs2[find2(i)].insert(find1(i));
    }

    vector<vector<int>> res(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        if (clubs2[i].size() > 1) {
            if (clubs2.size() == 2) return 0;
            ll prev = *--clubs2[i].end();
            for (auto &e : clubs2[i]) {
                if (res[prev][e]) return 0;
                res[prev][e] = 1;
                res[e][prev] = 1;
                unite2(e, prev);
                prev = e;
            }
        }
        if (clubs1[i].size() > 1) {
            ll prev = -1;
            for (auto &e : clubs1[i]) {
                if (prev != -1) {
                    if (res[prev][e]) return 0;
                    res[prev][e] = 1;
                    res[e][prev] = 1;
                    unite2(e, prev);
                }
                prev = e;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (p[i][j] == 0 && find2(i) == find2(j)) return 0;
            if (p[i][j] == 2 && find1(i) == find1(j)) return 0;
        }
    }

    build(res);
    return 1;
}

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