Submission #1007441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007441		u_suck_o	Connecting Supertrees (IOI20_supertrees)	C++17	19 / 100	117 ms	22100 KiB

supertrees

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

using namespace std;

int N;
int sizes[MAXN], par[MAXN];
vector<int> comps[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);
        }
    }
    
    //build components
    for (int i = 0; i < N; i++)
        comps[find(i)].push_back(i);
    for (int i = 0; i < N; i++) {
        if (comps[i].size() == 2)
            return 0;
        for (int j = 0; j < ((int) comps[i].size())-1; j++) {
            answer[comps[i][j]][comps[i][j+1]] = 1;
            answer[comps[i][j+1]][comps[i][j]] = 1;
        }
        if (comps[i].size() >= 3) {
            answer[comps[i][0]][comps[i][comps[i].size()-1]] = 1;
            answer[comps[i][comps[i].size()-1]][comps[i][0]] = 1;
        }
    }
    
    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: 0 / 11
• Subtask 2: 0 / 10
• Subtask 3: 19 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4