Submission #1198868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198868		ElayV13	슈퍼트리 잇기 (IOI20_supertrees)	C++20	19 / 100	123 ms	30148 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++)
        {
                if(comp[i].size() <= 2)
                {
                        for(int v : comp[i])
                        {
                                for(int u : comp[i])
                                {
                                        if(p[u][v] == 2) return 0;
                                }
                        }
                }
        }
        for(int i = 1;i <= c;i++)
        {
                bool req = 0;
                for(int u : comp[i])
                {
                        for(int v : comp[i])
                        {
                                if(p[u][v] == 2) req = 1;
                        }
                }
                if(!req) continue;
                for(int j = 0;j < comp[i].size() - 1;j++)
                {
                        b[comp[i][j]][comp[i][j + 1]] = 1;
                        b[comp[i][j + 1]][comp[i][j]] = 1;
                }
                b[comp[i][0]][comp[i][comp[i].size() - 1]] = 1;
                b[comp[i][comp[i].size() - 1]][comp[i][0]] = 1;
        }
        build(b);
        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