Submission #810985

#	Time	Username	Problem	Language	Result	Execution time	Memory
810985		oscar1f	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	209 ms	28328 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>

using namespace std;
using vv=vector<vector<int>>;

const int MAX_SOM=1005;
int nbSom;
vv adja,rep;
int pere[MAX_SOM][2];
vector<int> listeFils[MAX_SOM],listeBoucle[MAX_SOM];

int find(int pos,int tab) {
	if (pere[pos][tab]!=pos) {
		pere[pos][tab]=find(pere[pos][tab],tab);
	}
	return pere[pos][tab];
}

int construct(vv p) {
	adja=p;
	nbSom=adja.size();
	for (int i=0;i<nbSom;i++) {
		rep.push_back({});
		for (int j=0;j<nbSom;j++) {
			rep.back().push_back(0);
		}
		pere[i][0]=i;
		pere[i][1]=i;
	}
	for (int i=0;i<nbSom;i++) {
		for (int j=i+1;j<nbSom;j++) {
			if (adja[i][j]==3) {
				return 0;
			}
			if (adja[i][j]==1) { 
				if (find(i,0)!=find(j,0)) {
					pere[find(i,0)][0]=find(j,0);
				}
			}
		}
	}	
	for (int i=0;i<nbSom;i++) {
		//cout<<i<<" : "<<find(i,0)<<endl;
		listeFils[find(i,0)].push_back(i);
	}
    for (int i=0;i<nbSom;i++) {
        for (int j=1;j<(int)listeFils[i].size();j++) {
            for (int k=0;k<nbSom;k++) {
                if (adja[listeFils[i][j]]!=adja[listeFils[i][j-1]]) {
                    return 0;
                }
            }
            rep[listeFils[i][j]][listeFils[i][j-1]]=1;
            rep[listeFils[i][j-1]][listeFils[i][j]]=1;
        }
    }
    for (int i=0;i<nbSom;i++) {
        for (int j=i+1;j<nbSom;j++) {
            if (!listeFils[i].empty() and !listeFils[j].empty() and adja[i][j]==2 and find(i,1)!=find(j,1)) {
                pere[find(i,1)][1]=find(j,1);
            }
        }
    }
    for (int i=0;i<nbSom;i++) {
        if (!listeFils[i].empty()) {
            listeBoucle[find(i,1)].push_back(i);
        }
    }
    for (int i=0;i<nbSom;i++) {
        if (listeBoucle[i].size()>1) {
            for (int j=0;j<(int)listeBoucle[i].size();j++) {
                rep[listeBoucle[i][j]][listeBoucle[i][(j+1)%listeBoucle[i].size()]]=1;
                rep[listeBoucle[i][(j+1)%listeBoucle[i].size()]][listeBoucle[i][j]]=1;
            }
        }
    }
	build(rep);
	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