Submission #1007440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007440		u_suck_o	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	116 ms	22104 KiB

supertrees

#include "supertrees.h"
#include "bits/stdc++.h"
#define MAXN 1005

using namespace std;

int N;
int sizes[MAXN], par[MAXN];
vector<vector<int>> answer;

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

void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return;
    answer[u][v] = 1;
    answer[v][u] = 1;
    if (sizes[u] > sizes[v]) {
        par[v] = u;
        sizes[u] += sizes[v];
    } else {
        par[u] = v;
        sizes[v] += sizes[u];
    }
}

int construct(vector<vector<int>> p) {
    N = p.size();
    answer = vector<vector<int>>(N, vector<int>(N, 0));
    
    for (int i = 0; i < N; i++) {
        par[i] = i;
        sizes[i] = 1;
    }
    
    for (int i = 0; i < N; i++) {
        for (int j = i+1; j < N; j++) {
            if (p[i][j])
                join(i, j);
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (p[i][j] && find(i) != find(j))
                return 0;
            if (!p[i][j] && find(i) == find(j))
                return 0;
        }
    }
    build(answer);
    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