Submission #1062551

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062551		TlenekWodoru	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	172 ms	24148 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;
int spojna[1009];
int spojna2[1009];
int maxx[1009];
vector<int>V[1009];
int n,h1,h2;
int construct(vector<vector<int>> p)
{
    n=p.size();
    vector<vector<int>>graf(n,vector<int>(n,0));
    for(int i=0;i<n;i++)
    {
        if(p[i][i]!=1){return 0;}
        for(int j=i+1;j<n;j++)
        {
            if(p[i][j]!=p[j][i]||p[i][j]==3){return 0;}
        }
    }
    h1=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(p[i][j]==0||i==j){continue;}
            if(spojna[i]!=0&&spojna[i]!=spojna[j]){return 0;}
            else if(spojna[i]==0){spojna[i]=spojna[j];}
        }
        if(spojna[i]==0){spojna[i]=++h1;}
    }
    h2=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(p[i][j]!=1||i==j){continue;}
            if(spojna2[i]!=0&&spojna2[i]!=spojna2[j]){return 0;}
            else if(spojna2[i]==0){spojna2[i]=spojna2[j];}
        }
        if(spojna2[i]==0){spojna2[i]=++h2;}
    }
    for(int i=0;i<n;i++)
    {
        for(int j=i+1;j<n;j++)
        {
            if(spojna[i]!=spojna[j]&&p[i][j]!=0){return 0;}
            if(spojna[i]==spojna[j]&&p[i][j]==0){return 0;}
            if(spojna2[i]==spojna2[j]&&p[i][j]!=1){return 0;}
            if(spojna2[i]==spojna2[j]&&spojna[i]!=spojna[j]){return 0;}
            if(spojna[i]==spojna[j]&&spojna2[i]!=spojna2[j]&&p[i][j]!=2){return 0;}
        }
    }
    memset(maxx,-1,sizeof(maxx));
    for(int i=0;i<n;i++)
    {
        maxx[spojna2[i]]=max(maxx[spojna2[i]],i);
    }
    for(int i=0;i<n;i++)
    {
        int u=maxx[spojna2[i]];
        if(u==i){continue;}
        graf[i][u]=1;
        graf[u][i]=1;
    }
    for(int i=1;i<=h1;i++)
    {
        vector<int>U;
        for(int j=0;j<n;j++)
        {
            if(spojna[j]!=i||maxx[spojna2[j]]!=j){continue;}
            U.push_back(j);
        }
        if((int)U.size()==2){return 0;}
        if((int)U.size()<=1){continue;}
        for(int j=0;j<(int)U.size();j++)
        {
            int u=U[j],last;
            if(j==0){last=U.back();}
            else{last=U[j-1];}
            graf[u][last]=1;
            graf[last][u]=1;
        }
    }
    build(graf);
    return 1;
}

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