Submission #1224328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224328		PVM_pvm	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	126 ms	26128 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1002
vector<int> komp;
vector<int> komp2;
bool bb[MAXN];
bool bb2[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);
    }
}
void dfs2(int x)
{
    komp2.push_back(x);
    bb2[x]=1;
    for (int q=0;q<N;q++)
    {
        if (sys[x][q]==0) continue;
        if (sys[x][q]==2) continue;
        if (bb2[q]) continue;
        dfs2(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++)
    {
        for (int w=0;w<n;w++)
        {
            if (p[q][w]==3) return 0;
        }
    }
    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;
                }
            }
        }
        vector<int> specialisti;
        for (int ww=0;ww<komp.size();ww++)
        {
            int w=komp[ww];
            if (bb2[w]) continue;
            komp2.clear();
            dfs2(w);
            for (int e=0;e<komp2.size();e++)
            {
                for (int r=0;r<komp2.size();r++)
                {
                    if ( p[ komp2[e] ][ komp2[r] ]==2 ) return 0;
                }
            }
            specialisti.push_back(komp2[0]);
            for (int e=0;e<komp2.size()-1;e++)
            {
                answer[ komp2[e] ][ komp2[e+1] ]=1;
                answer[ komp2[e+1] ][ komp2[e] ]=1;
            }
        }
        if (specialisti.size()==2) return 0;
        if (specialisti.size()!=1) specialisti.push_back(specialisti[0]);
        for (int w=0;w<specialisti.size()-1;w++)
        {
            answer[ specialisti[w] ][ specialisti[w+1] ]=1;
            answer[ specialisti[w+1] ][ specialisti[w] ]=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