제출 #1231513

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231513		abdelhakim	슈퍼트리 잇기 (IOI20_supertrees)	C++20	11 / 100	119 ms	26196 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())
        {
            // cout << "groupe i " << i << endl;
            // for (auto &&e : grps[i])
            // {
            //     dbg(e);
            // }
            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;
                // possible=false;
                continue;
            }
            vector<vector<ll>> ts(3,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
                {
                    if(g!=0)
                    {
                        ts[2].push_back(e);
                        tp[e]=2;
                    }
                    else
                    {
                        ts[0].push_back(e);
                        tp[e]=0;
                        g++;
                        for (int j=0;j<n;j++)
                        {
                            if(j==e)continue;
                            if(v[e][j]==1)
                            {
                                ts[0].push_back(j);
                                tp[j]=0;
                            }
                        }
                    }
                }
            }
            for (int j=0;j<3;j+=2)
            {
                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[0].size())
            {
                ts[1].insert(ts[1].begin(),ts[0].back());
            }
            if(ts[2].size())
            {
                ts[1].push_back(ts[2][0]);
            }
            // dbg(ts[1].size());
            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++)
    // {
    //     cout << "i " << i << ' ' << tp[i] << endl;
    // }
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
        {
            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(1)
    {
        build(b);
    }
    return 1;
}

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