제출 #1231532

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231532		abdelhakim	슈퍼트리 잇기 (IOI20_supertrees)	C++20	100 / 100	121 ms	26216 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define dbg(x) cerr << #x << ' ' << x << endl;
using namespace std;
vector<vector<ll>> grps;
vector<ll> component;
vector<bool> vis;
vector<vector<int>> v;
vector<int> tp;
void dfs(ll node, ll cur)
{
    vis[node]=1;
    component[node]=cur;
    grps[cur].push_back(node);
    for (int i=0;i<v.size();i++)
    {
        if(i==node)continue;
        if(v[node][i] && !vis[i])
        {
            dfs(i,cur);
        }
    }
}
int construct(std::vector<std::vector<int>> p)
{
    ll n=p.size();
    v=p;
    tp.assign(n,-1);
    grps.resize(n);
    component.resize(n);
    vis.resize(n);
    ll cur=0;
    for (int i=0;i<n;i++)
    {
        if(vis[i])continue;
        dfs(i,cur);
        cur++;
    }
    bool possible=true;
    vector<vector<int>> b(n,vector<int>(n,0));
    for (int i=0;i<n;i++)
    {
        if(grps[i].size())
        {
            if(grps[i].size()==1)continue;
            if(grps[i].size()==2)
            {
                tp[grps[i][0]]=0;
                tp[grps[i][1]]=0;
                b[grps[i][0]][grps[i][1]]=1;
                b[grps[i][1]][grps[i][0]]=1;
                continue;
            }
            vector<vector<ll>> ts(n,vector<ll>());
            ll g=0;
            for (auto &&e : grps[i])
            {
                if(tp[e]!=-1)continue;
                bool all=true;
                for (int j=0;j<n;j++) {if(j==e)continue;all&=!(v[e][j]==1);}
                if(all) 
                {
                    ts[1].push_back(e);
                    tp[e]=1;
                }
                else
                {
                    ts[g].push_back(e);
                    tp[e]=g;
                    for (int j=0;j<n;j++)
                    {
                        if(j==e)continue;
                        if(v[e][j]==1)
                        {
                            ts[g].push_back(j);
                            tp[j]=g;
                        }
                    }
                    if(g==0) g+=2;
                    else g++;
                }
            }
            for (int j=0;j<n;j++)
            {
                for (int ii=1;ii<ts[j].size();ii++)
                {
                    ll n1=ts[j][ii];
                    ll n2=ts[j][ii-1];
                    b[n1][n2]=1;
                    b[n2][n1]=1;
                }
                if(ts[j].size())
                {
                    ts[1].push_back(ts[j].back());
                }
                if(j==0)j++;
            }
            if(ts[1].size()==2)possible=false;
            for (int ii=0;ii<ts[1].size();ii++)
            {
                ll n1=ts[1][ii];
                ll n2=ts[1][(ii+1)%ts[1].size()];
                b[n1][n2]=1;
                b[n2][n1]=1;
            }
        }
    }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
            if(p[i][j]==3)possible=false;
            if(i==j) {b[i][j]=0;continue;}
            ll l3iba=0;
            if(component[i]==component[j])
            {
                if(tp[i]==tp[j])
                {
                    if(tp[i]==1) l3iba=2;
                    else l3iba=1;
                }
                else
                {
                    l3iba=2;
                }
            }
            else
            {
                l3iba=0;
            }
            possible&=(v[i][j]==l3iba);
        }
        
    }
    if(possible)
    {
        build(b);
    }
    return possible;
}

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