Submission #1201774

#	Time	Username	Problem	Language	Result	Execution time	Memory
1201774		Triseedot	Connecting Supertrees (IOI20_supertrees)	C++20	56 / 100	123 ms	22180 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 (anc[v] != anc[u]) {
                    return 0;
                }
            }
        }
    }

    for (int i = 0; i < k; i++) {
        vector<int> anc1(n, -1);
        vector<vector<int>> child1;
        int l = 0;

        for (int v : child[i]) {
            if (anc1[v] != -1) continue;
            anc1[v] = l++;
            child1.push_back({});
            for (int u : child[i]) {
                if (p[v][u] == 1) {
                    anc1[u] = l - 1;
                    child1[l - 1].push_back(u);
                }
            }
        }

        for (int v : child[i]) {
            for (int u : child[i]) {
                if (p[v][u] == 2) {
                    if (anc1[v] == anc1[u]) {
                        return 0;
                    }
                }
                else if (p[v][u] == 1) {
                    if (anc1[v] != anc1[u]) {
                        return 0;
                    }
                }
                else {
                    return 0;
                }
            }
        }

        for (int j = 0; j < l; j++) {
            for (int x = 0; x + 1 < len(child1[j]); x++) {
                int v = child1[j][x], u = child1[j][x + 1];
                ans[v][u] = 1;
                ans[u][v] = 1;
            }
            if (l != 1) {
                int j1 = (j + 1) % l;
                int v = child1[j][0], u = child1[j1][0];
                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: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4