Submission #1224316

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224316		PVM_pvm	Connecting Supertrees (IOI20_supertrees)	C++20	19 / 100	119 ms	26092 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1002
vector<int> komp;
bool bb[MAXN];
int N;
vector<vector<int>> sys;
void dfs(int x)
{
    komp.push_back(x);
    bb[x]=1;
    for (int q=0;q<N;q++)
    {
        if (sys[x][q]==0) continue;
        if (bb[q]) continue;
        dfs(q);
    }
}
int construct(vector<vector<int>> p) {
    sys=p;
	int n = p.size();
    N=n;
    vector<vector<int>> answer;
    for (int q=0;q<n;q++)
    {
        vector<int> ans2;
        ans2.resize(n);
        for (int w=0;w<n;w++) ans2[w]=0;
        answer.push_back(ans2);
    }
    for (int q=0;q<n;q++)
    {
        ///reshili sme za pred komponenta
        if (bb[q]) continue;
        komp.clear();
        dfs(q);
        for (int w=0;w<komp.size();w++)
        {
            for (int e=0;e<komp.size();e++)
            {
                if (p[komp[w]][komp[e]]==0)
                {
                    return 0;
                }
            }
        }
        if (komp.size()==2) return 0;
        if (komp.size()!=1) komp.push_back(komp[0]);
        for (int w=0;w<komp.size()-1;w++)
        {
            answer[ komp[w] ][ komp[w+1] ]=1;
            answer[ komp[w+1] ][ komp[w] ]=1;
        }
    }
    build(answer);
	return 1;
}

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