Submission #385712

#	Time	Username	Problem	Language	Result	Execution time	Memory
385712		AlexRex0	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	290 ms	22372 KiB

supertrees

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

int n;
int link[1002];
int setSize[1002];

void init(){
    for(int i = 0; i < n; ++i){
        link[i] = i;
        setSize[i] = 1;
    }
}

int root(int u){
    if(link[u] == u){
        return u;
    }else{
        link[u] = root(link[u]);
        return link[u];
    }
}

bool same(int u, int v){
    int rU = root(u);
    int rV = root(v);
    return rU == rV;
}

void unite(int u, int v){
    u = root(u);
    v = root(v);
    if(setSize[v] > setSize[u]){
        swap(u,v);
    }
    setSize[u] += setSize[v];
    link[v] = u;
}


int construct(vector< vector<int> > p) {
	n = p.size();
	vector< vector <int> > answer;
	for(int i = 0; i < n; ++i){
        vector<int> aux(n, 0);
        answer.push_back(aux);
	}
	init();
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(p[i][j] == 1 && !same(i, j)){
                unite(i, j);
                answer[i][j] = 1;
                answer[j][i] = 1;
            }
        }
    }
    bool valido = true;
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(p[i][j] == 0 && same(i, j)){
                valido = false;
            }
        }
    }
    if(valido){
        build(answer);
        return 1;
    }else{
        return 0;
    }
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4