Submission #371144

#	Time	Username	Problem	Language	Result	Execution time	Memory
371144		Ozy	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	275 ms	24300 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define debug(a) cout << #a << " " <<  a << endl
#define nl "\n"

lli n,ult,a,b,c,d;
lli padre[1002],grupo[1002],visitados[1002],inicios[1002],finales[1002],cant[1002];
bool res;
vector<lli> cabezas;

void procesa(lli act) {
    if (padre[act] != act) {
        procesa(padre[act]);
        padre[act] = ult;
    }
    else ult = act;
}

void calcula(lli act) {
    if (grupo[act] != act) {
        calcula(grupo[act]);
        grupo[act] = ult;
    }
    else ult = act;
}

int construct(std::vector<std::vector<int>> p) {

	res = true;
	n = p.size();
	vector<vector<int> > puentes(n, vector<int> (n, 0));
    rep(i,0,n-1) padre[i] = i;
    rep(i,0,n-1) grupo[i] = i;

	rep(i,0,n-1) {
        rep(j,i,n-1){
            if (visitados[j] == 1) continue;
            if (i == j) continue;

            if (p[i][j] != p[j][i]) res = false;
            if (p[i][j] == 3) res = false;
            if (res == false) return 0;

            if (p[i][j] == 1) {
                padre[j] = i;
                puentes[i][j] = 1;
                puentes[j][i] = 1;
                visitados[j] = 1;
            }
        }
	}


	rep(i,0,n-1) {

	    if (padre[i] != i) continue;

        rep(j,i,n-1){
            if (i == j) continue;
            if (padre[i] != i) continue;
            if (visitados[j] == 2) continue;


            if (p[i][j] == 2) {
                grupo[j] = i;
                visitados[j]=2;
            }
        }
	}

	rep(i,0,n-1) {
	    rep(j,i,n-1) {
	        if(i == j) continue;

            procesa(i);
            a = ult;
            procesa(j);
            b = ult;

            calcula(a);
            c = ult;
            calcula(b);
            d = ult;


            if (p[i][j] == 0){
                if (a != b && c != d) continue;
                else res = false;
            }
            else if (p[i][j] == 1){
                if (a == b && c == d) continue;
                else res = false;
            }
            else {
                if (a != b && c == d) continue;
                else res = false;
            }

            if (!res) return 0;
	    }
	}

	rep(i,0,n-1) {
        if (padre[i] == i) {

            calcula(i);

            if (cant[ult] == 0) {
                inicios[ult] = i;
                finales[ult] = i;
                cant[ult] = 1;
            }
            else {
                puentes[i][finales[ult]] = 1;
                puentes[finales[ult]][i] = 1;
                //cout << ult << ' ' << finales[ult] << endl;

                finales[ult] = i;
                cant[ult]++;
            }

        }
	}

	rep(i,0,n-1) {
        if (cant[i] == 2) return 0;

        if (cant[i] > 2) {
            puentes[finales[i]][inicios[i]] = 1;
            puentes[inicios[i]][finales[i]] = 1;
        }
	}

	build(puentes);
	return 1;
}

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