Submission #1201768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201768		Triseedot	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	117 ms	22192 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define len(v) (int) (v.size())

int construct(vector<vector<int>> p) {
	int n = len(p);
	vector ans(n, vector(n, 0));

    vector<int> anc(n, -1);
    vector<vector<int>> child;
    int k = 0;

    for (int v = 0; v < n; v++) {
        if (anc[v] != -1) continue;
        anc[v] = k++;
        child.push_back({});
        for (int u = 0; u < n; u++) {
            if (p[v][u] != 0) {
                anc[u] = k - 1;
                child[k - 1].push_back(u);
            }
        }
    }

    for (int v = 0; v < n; v++) {
        for (int u = 0; u < n; u++) {
            if (p[v][u] == 0) {
                if (anc[v] == anc[u]) {
                    return 0;
                }
            }
            else if (p[v][u] <= 2) {
                if (anc[v] != anc[u]) {
                    return 0;
                }
            }
            else {
                return 0;
            }
        }
    }

    for (int i = 0; i < k; i++) {
        for (int j = 0; j + 1 < len(child[i]); j++) {
            int v = child[i][j];
            int u = child[i][j + 1];
            ans[v][u] = 1;
            ans[u][v] = 1;
        }
    }

    build(ans);
	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