Submission #308544

#	Time	Username	Problem	Language	Result	Execution time	Memory
308544		Peti	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	284 ms	22268 KiB

supertrees

#include "supertrees.h"
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

struct union_find{
    vector<int> csop, mely;

    void Init(int n){
        csop.resize(n, -1);
        mely.resize(n, 0);
        return;
    }

    int Os(int a){
        if(csop[a] == -1)
            return a;
        csop[a] = Os(csop[a]);
        return csop[a];
    }

    bool Union(int a, int b)
    {
        a = Os(a);
        b = Os(b);

        if(a == b)
            return false;

        if(mely[a] < mely[b])
            swap(a, b);
        csop[b] = a;
        mely[a] = max(mely[a], mely[b]+1);
        return true;
    }
};

vector<int> Halmaz(vector<int> &inds, union_find &csop, int c)
{
    vector<int> ret;

    for(int x : inds)
        if(csop.Os(x) == c)
            ret.push_back(x);

    return ret;
}

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

    union_find csop;
    csop.Init(n);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(p[i][j] == 3 || (i == j && p[i][j] != 1))
                return 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = i+1; j < n; j++)
        {
            if(p[i][j] == 1)
            {
                int x = csop.Os(i), y = csop.Os(j);
                if(csop.Union(x, y))
                {
                    answer[x][y] = 1;
                    answer[y][x] = 1;
                }
            }
        }
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == j)
                continue;

            if(csop.Os(i) == csop.Os(j) && p[i][j] != 1)
                return 0;
        }
    }

    vector<int> inds;
    for(int i = 0; i < n; i++)
        if(csop.Os(i) == i)
            inds.push_back(i);

    union_find csop2;
    csop2.Init(n);

    for(int i = 0; i < n; i++)
        for(int j = i+1; j < n; j++)
            if(p[i][j] == 2)
                csop2.Union(csop.Os(i), csop.Os(j));

    /*for(int i = 0; i < n; i++)
        cout<<csop.Os(i)<<" ";
    cout<<"\n";*/

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(i == j)
                continue;

            if(csop.Os(i) != csop.Os(j) && csop2.Os(csop.Os(i)) == csop2.Os(csop.Os(j)) && p[i][j] != 2)
                return 0;
        }
    }

    for(int i : inds)
    {
        if(csop2.Os(i) == i)
        {
            vector<int> v = Halmaz(inds, csop2, i);

            if(v.size() == 1)
                continue;
            if(v.size() == 2)
                return 0;

            for(int j = 0; j < (int)v.size()-1; j++)
            {
                answer[v[j]][v[j+1]] = 1;
                answer[v[j+1]][v[j]] = 1;
            }
            answer[v[0]][(*v.rbegin())] = 1;
            answer[(*v.rbegin())][v[0]] = 1;
        }
    }

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