Submission #1198860

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198860		ElayV13	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	122 ms	30160 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1001;

int n = -1 , c = 0;
vector < int > adj[N];
bool vis[N];
vector < vector < int > > comp(N);
vector < vector < int > > b;

void dfs(int v)
{
        comp[c].push_back(v);
        vis[v] = 1;
        for(int u : adj[v])
        {
                if(!vis[u]) dfs(u);
        }
}

int construct(vector < vector < int > > p)
{
        n = p.size();
        b.assign(n , vector < int > (n , 0));
        for(int i = 0;i < n;i++)
        {
                for(int j = 0;j < n;j++)
                {
                       if(p[i][j]) adj[i].push_back(j) , adj[j].push_back(i);
                }
        }
        for(int i = 0;i < n;i++)
        {
                if(!vis[i])
                {
                        ++c;
                        dfs(i);
                }
        }
        for(int i = 1;i <= c;i++)
        {
                for(int x : comp[i])
                {
                        for(int y : comp[i])
                        {
                                if(p[x][y] == 0) return 0;
                        }
                }
        }
        for(int i = 1;i <= c;i++)
        {
                int v = comp[i][0];
                for(int x : comp[i])
                {
                        if(x == v) continue;
                        b[v][x] = 1;
                        b[x][v] = 1;
                }
        }
        build(b);
        return 1;
}

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