Submission #430608

#	Time	Username	Problem	Language	Result	Execution time	Memory
430608		Ozy	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	315 ms	22692 KiB

supertrees

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

#define MAX 1000

lli n,m,ult,pos,pp,cant;
lli visitados[MAX+2];
vector<lli> cabezas;
vector<vector<lli> > planos;

bool compara(lli a, lli b, lli tipo,vector<vector<lli> > &pl) {

    lli q,w;

    rep(i,0,n-1) {

        if (pl[a][i] == 3 || pl[b][i] == 3) return false;

        if (tipo == 1) {
            if (pl[a][i] != pl[b][i]) return false;
        }
        else {
            if (pl[a][i] > 0) q = 1;
            else q = 0;

            if (pl[b][i] > 0) w = 1;
            else w = 0;

            if (q != w) return false;
        }

    }

    return true;
}

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

	n = p.size();
	planos = vector< vector<lli> > (n, vector<int> (n,0));

	//hacer cabezas
	rep(i,0,n-1) {
        if (visitados[i] == 0) {

            cabezas.push_back(i);
            visitados[i] = 1;
            rep(j,0,n-1) {
                if (p[i][j] == 3) return 0;
                if (j == i || p[i][j] != 1) continue;

                visitados[j] = 1;
                if (!compara(i,j,1,p)) return 0;
                else {
                    planos[i][j] = 1;
                    planos[j][i] = 1;
                }
            }

        }
	}


	m = cabezas.size();
	rep(i,0,m-1) {
        pos = cabezas[i];

        if (visitados[pos] < 2) {

            ult = pos;
            visitados[pos] = 2;
            cant = 0;

            rep(j,0,m-1) {
                pp = cabezas[j];
                if (pos == pp || p[pos][pp] != 2) continue;

                cant++;
                visitados[pp] = 2;
                if (!compara(pos,pp,2,p)) return 0;
                else {
                    planos[ult][pp] = 1;
                    planos[pp][ult] = 1;
                    ult = pp;
                }

            }

            if (cant == 1) return 0;
            if (pos != ult) {
                planos[pos][ult] = 1;
                planos[ult][pos] = 1;
            }

        }

	}


	build(planos);
	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