Submission #586757

#	Time	Username	Problem	Language	Result	Execution time	Memory
586757		PiejanVDC	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	211 ms	23980 KiB

supertrees

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

void build(std::vector<std::vector<int>> _b);

vector<int>par;
vector<int>cpar;

int UF(int u) {
    if(par[u] == u)
        return u;
    return par[u] = UF(par[u]);
}

int CUF(int u) {
    if(cpar[u] == u)
        return u;
    return cpar[u] = CUF(cpar[u]);
}

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

    par.resize(n);
    cpar.resize(n);

    vector<bool>has_cycle(n,0);

    for(int i = 0 ; i < n ; i++)
        par[i] = cpar[i] = i;

    bool ok = 1;

    vector<vector<int>>ans(n, vector<int>(n,0));

    for(int i = 0 ; i < n ; i++) {
        for(int j = i+1 ; j < n ; j++) {
            if(p[i][j] == 3)
                ok = 0;
            if(p[i][j] == 1) {
                int A = UF(i), B = UF(j);
                if(A == B)
                    continue;
                ans[i][j] = ans[j][i] = 1;
                par[A] = B;
            }
        }
    }

    for(int i = 0 ; i < n ; i++) {
        for(int j = i+1 ; j < n ; j++) {
            if(p[i][j] == 2) {
                int A = CUF(UF(i)), B = CUF(UF(j));
                if(A == B)
                    continue;
                cpar[A] = B;
            }
        }
    }

    for(int i = 0 ; i < n ; i++) {
        for(int j = i+1 ; j < n ; j++) {
            int A = UF(i), B = UF(j);
            if(A == B && p[i][j] != 1)
                ok = 0;
            A = CUF(i), B = CUF(j);
            if(A == B)
                has_cycle[i] = has_cycle[j] = 1;
            if(A == B && p[i][j] != 2)
                ok = 0;
        }
    }

    for(int i = 0 ; i < n ; i++) {
        for(int j = i+1 ; j < n ; j++) {
            if(p[i][j] == 0 && has_cycle[UF(i)])
                ok = 0;
        }
    }

    for(int i = 0 ; i < n ; i++) {
        if(CUF(i) != i)
            continue;
        int f = -1, l = -1;
        for(int j = 0 ; j < n ; j++) {
            if(CUF(j) == i) {
                if(f == -1)
                    f = j;
                if(l != -1)
                    ans[l][j] = ans[j][l] = 1;
                l = j;
            }
        }

        if(f == l)
            continue;
        ans[l][f] = ans[f][l] = 1;
    }
    if(ok) {
        build(ans);
        return 1;
    }
    return 0;
}

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