Submission #1145935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145935		AlgorithmWarrior	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	135 ms	22216 KiB

supertrees

#include <bits/stdc++.h>
#include <vector>
#define MAX 1005

using namespace std;

vector<int>team_type1[MAX];
int N;
int nbt[MAX];
bool vis[MAX];
vector<vector<int>>answer;

void myfill2(int nod,vector<int>&nodes,vector<int>&put_val,vector<vector<int>>&p)
{
    put_val.push_back(nod);
    vis[nod]=1;
    for(auto el : nodes)
        if(p[nod][el]==1 && !vis[el])
            myfill2(el,nodes,put_val,p);
}

bool solve_connected_component(vector<int>&nodes,vector<vector<int>>&p)
{
    vector<int>put_val;
    int i;
    int primul=-1,ult=-1;
    int cnt=0;
    for(auto el : nodes)
        if(!vis[el])
        {
            ++cnt;
            myfill2(el,nodes,put_val,p);
            for(auto el1 : put_val)
                for(auto el2 : put_val)
                    if(p[el1][el2]==2)
                        return 0;
            for(i=1;i<put_val.size();++i)
                answer[put_val[i-1]][put_val[i]]=answer[put_val[i]][put_val[i-1]]=1;
            if(primul>-1)
            {
                answer[ult][put_val[0]]=answer[put_val[0]][ult]=1;
                ult=put_val[0];
            }
            else
                primul=ult=put_val[0];
            put_val.clear();
        }
    /// VERIFICA CNT SA NU FIE 2
    if(cnt==2)
        return 0;
    if(primul!=ult)
        answer[primul][ult]=answer[ult][primul]=1;
    return 1;
}

void myfill(int nod,vector<vector<int>>&path,int nbteam)
{
    team_type1[nbteam].push_back(nod);
    nbt[nod]=nbteam;
    int i;
    for(i=0;i<N;++i)
        if(!nbt[i] && path[i][nod])
            myfill(i,path,nbteam);
}

void debug()
{
    int i,j;
    for(i=0;i<N;++i){
        for(j=0;j<team_type1[i].size();++j)
            cout<<team_type1[i][j]<<' ';
        cout<<'\n';
    }
}

bool check_type_1(vector<vector<int>>&p)
{
    int i,j;
    for(i=0;i<N;++i)
        for(j=0;j<N;++j)
            if(!p[i][j] && nbt[i]==nbt[j])
                return 0;
    return 1;
}

void build(vector<vector<int>>b);

int construct(vector<vector<int>>p)
{
    int i,j;
    N=p[0].size();
    for(i=0;i<N;++i)
        for(j=0;j<N;++j)
            if(p[i][j]==3)
                return 0;
    answer.resize(N);
    for(i=0;i<N;++i)
        answer[i].resize(N);
    int team=0;
    for(i=0;i<N;++i)
        if(!nbt[i])
            myfill(i,p,++team);
    if(!check_type_1(p))
        return 0;
    for(i=1;i<=team;++i)
        if(!solve_connected_component(team_type1[i],p))
            return 0;
    build(answer);
    return 1;
}

/*
int main()
{
    int NN;
    cin>>NN;
    vector<vector<int> >mat;
    mat.resize(NN);
    int i;
    for(i=0;i<NN;++i)
        mat[i].resize(NN);
    int j;
    for(i=0;i<NN;++i)
        for(j=0;j<NN;++j)
            cin>>mat[i][j];
    cout<<construct(mat);
    return 0;
}
*/

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