Submission #666525

#	Time	Username	Problem	Language	Result	Execution time	Memory
666525		YENGOYAN	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	221 ms	24000 KiB

supertrees

#include "supertrees.h"
#include <vector>

using namespace std;

vector<int> par, sizes;

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

void union_sets(int u, int v){
    int a = get(u), b = get(v);
    if(a == b) return;
    if(sizes[a] < sizes[b]) swap(a, b);
    par[b] = a;
    sizes[a] += sizes[b];
}

int construct(vector<std::vector<int>> p) {
	int n = p.size();
	vector<vector<int>> gp(n, vector<int> (n));
	par = sizes = vector<int> (n);
	for(int i = 0; i < n;i++) par[i] = i, sizes[i] = 1;
	for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            if(!p[i][j]) continue;
            int u = get(i), v = get(j);
            if(u != v) union_sets(u, v), gp[i][j] = gp[j][i] = 1;
        }
	}
	for(int i = 0; i < n;i++){
        for(int j = 0; j < n;j++){
            int u = get(i), v = get(j);
            if((u == v) != p[i][j]) return 0;
        }
	}
	build(gp);
	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