Submission #305420

#	Time	Username	Problem	Language	Result	Execution time	Memory
305420		diegoangulo5	Connecting Supertrees (IOI20_supertrees)	C++14	0 / 100	1086 ms	12408 KiB

supertrees

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

using namespace std;

vector< vector<int> > answer;
vector< set<int> >nodos1, nodos2;
vector<int> padre1, padre2, row;
int n;

void init(){
    nodos1.resize(n);
    nodos2.resize(n);
    padre1.resize(n);
    padre2.resize(n);
    row.resize(n);
    for(int a=0;a<n;a++){
        nodos1[a].insert(a);
        nodos2[a].insert(a);
        padre1[a] = a;
        padre2[a] = a;
		answer.push_back(row);
    }
}

set<int> juntar(set<int> a, set<int> b){
    set<int> :: iterator it = b.begin();
    for(;it != b.end();it++){
        a.insert(*it);
    }
    return a;
}

int buscar2(int a){
    if(padre2[a] == a)return a;
    return padre2[a] = buscar2(padre2[a]);
}

void unir2(int a, int b){
    int A = buscar2(a);
    int B = buscar2(b);
    if(A != B){
        padre2[max(A,B)] = min(A,B);
        nodos2[min(A,B)] = juntar(nodos2[A], nodos2[B]);
        nodos2[max(A,B)].clear();
    }
}

int buscar1(int a){
    if(padre1[a] == a)return a;
    return padre1[a] = buscar1(padre1[a]);
}

void unir1(int a, int b){
    int A = buscar1(a);
    int B = buscar1(b);
    if(A != B){
        padre1[max(A,B)] = min(A,B);
        nodos1[min(A,B)] = juntar(nodos1[A], nodos1[B]);
        nodos1[max(A,B)].clear();
    }
}

void crear2(){
    for(int a=0;a<n;a++){
        if(nodos2[a].size() > 1){
            set<int>::iterator it = nodos2[a].begin();
            int anterior = *it;
            it++;
            for(;it != nodos2[a].end();it++){
                answer[anterior][*it] = 1;
                answer[*it][anterior] = 1;
                anterior = *it;
            }
            it--;
            answer[*it][*nodos2[a].begin()] = 1;
            answer[*nodos2[a].begin()][*it] = 1;
        }
    }
}

void crear1(){
    for(int a=0;a<n;a++){
        if(nodos1[a].size() > 1){
            set<int>::iterator it = nodos1[a].begin();
            int anterior = *it;
            it++;
            for(;it != nodos1[a].end();it++){
                answer[anterior][*it] = 1;
                answer[*it][anterior] = 1;
                //anterior = *it;
            }
        }
    }
}

int construct(vector<vector<int> > p) {
	n = p.size();
    init();
    for(int a=0;a<n;a++){
        for(int b=0;b<n;b++){
            int val = p[a][b];
            if(p[a][b] != p[b][a])return 0;
            if(val == 0){
                if(a == b)return 0;
            }
            if(val == 1){
                unir1(a, b);
            }
            if(val == 2){
                if(a == b)return 0;
                unir2(a, b);
            }
        }
    }
    for(int a=0;a<n;a++){
        for(int b=0;b<n;b++){
            for(int c=0;c<n;c++){
                if(p[a][b] == p[b][c] && p[a][c] != p[a][b])return 0;
            }
        }
    }
    crear2();
    crear1();
	build(answer);
	return 1;
}

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