Submission #1239496

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239496		Ghulam_Junaid	Connecting Supertrees (IOI20_supertrees)	C++20	56 / 100	141 ms	22196 KiB

supertrees

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

const int N = 1e3 + 10;
int n, par[N][3];
vector<vector<int>> output;

int root(int v, int id){
    return (par[v][id] == -1 ? v : par[v][id] = root(par[v][id], id));
}

void merge(int u, int v, int id){
    if ((u = root(u, id)) == (v = root(v, id)))
        return ;
    par[u][id] = v;
}

int construct(vector<vector<int>> p) {
	n = p.size();
    output.resize(n);
	for (int i = 0; i < n; i++)
		output[i].resize(n);

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (p[i][j] == 3)
                return 0;

    for (int v = 0; v < n; v ++)
        par[v][0] = par[v][1] = -1;
    for (int i = 0; i < n; i ++){
        for (int j = 0; j < n; j ++){
            if (p[i][j])
                merge(i, j, 0);
            if (p[i][j] == 1)
                merge(i, j, 1);
        }
    }

    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (p[i][j] == 0 and root(i, 0) == root(j, 0))
                return 0;

    for (int rr = 0; rr < n; rr ++){
        vector<int> comp;
        for (int i = 0; i < n; i ++)
            if (root(i, 0) == rr)
                comp.push_back(i);
        if (comp.empty()) continue;

        vector<int> roots;
        for (int u : comp){
            vector<int> small_comp;
            for (int v : comp){
                if (root(v, 1) == u)
                    small_comp.push_back(v);
            }
            if (small_comp.empty()) continue;
            
            roots.push_back(u);
            for (int v : small_comp)
                if (u != v)
                    output[u][v] = output[v][u] = 1;
        }

        int sz = roots.size();
        for (int i = 0; i < sz and sz > 2; i ++)
            output[roots[i]][roots[(i + 1) % sz]] = output[roots[(i + 1) % sz]][roots[i]] = 1;
    }

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