Submission #300657

#	Time	Username	Problem	Language	Result	Execution time	Memory
300657		CodePlatina	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	290 ms	22392 KiB

supertrees

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

using namespace std;

int par[1010];
vector<int> ls[1010];
int fnd(int x) { return x == par[x] ? x : par[x] = fnd(par[x]); }
void uni(int x, int y) { par[fnd(x)] = fnd(y); }

int construct(vector<vector<int>> p)
{
	int n = p.size();
	vector<vector<int>> ret(n, vector<int>(n));

	for(int i = 0; i < n; ++i) par[i] = i;
	for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(p[i][j] == 3) return 0;
            if(p[i][j]) uni(i, j);
        }
    }
    for(int i = 0; i < n; ++i) ls[fnd(i)].push_back(i);

    for(int i = 0; i < n; ++i) if(ls[i].size())
    {
        vector<int> tmp = ls[i];
        for(int j : tmp) for(int k : tmp) if(p[j][k] == 0) return 0;
        for(int j : tmp) par[j] = j, ls[j].clear();
        for(int j : tmp) for(int k : tmp) if(p[j][k] == 1) uni(j, k);
        for(int j : tmp) ls[fnd(j)].push_back(j);

        vector<int> head;
        for(int j : tmp) if(ls[j].size())
        {
            head.push_back(j);
            for(int k : ls[j]) for(int l : ls[j]) if(p[k][l] == 2) return 0;
            for(int k = 0; k < (int)ls[j].size() - 1; ++k) ret[ls[j][k]][ls[j][k + 1]] = ret[ls[j][k + 1]][ls[j][k]] = 1;
        }
        if(head.size() == 2) return 0;
        if(head.size() >= 3)
        {
            for(int j = 0; j < (int)head.size() - 1; ++j) ret[head[j]][head[j + 1]] = ret[head[j + 1]][head[j]] = 1;
            ret[head.back()][head[0]] = ret[head[0]][head.back()] = 1;
        }
    }

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