Submission #828648

#	Time	Username	Problem	Language	Result	Execution time	Memory
828648		Mularstyle	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	174 ms	24192 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
#define ll long long

using namespace std;
int C1[1008],C2[1008],P[1008];
bool vis[1008];
//int V[1008][1008];
vector<std::vector<int>> A;
void added(int u,int v)
{
    if(u==-1||v==-1)
        return;
    if(u==v)
        return;
    A[u][v]=1;
    A[v][u]=1;
    return;
}


int construct(std::vector<std::vector<int>> p) {
	int n = p.size();

	int cnt=0;
    A.resize(n);
    for(int i=0;i<n;i++)
    {
        A[i].resize(n);
        for(int j=0;j<n;j++)
            A[i][j]=0;
    }
    for(int i=0;i<n;i++)
    {
        if(C1[i]==0)cnt++;
        else continue;
        for(int j=0;j<n;j++)
        {
            if(p[i][j])
                C1[j]=cnt;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if((C1[i]==C1[j])^(p[i][j]!=0))
                return 0;//impos
            if(p[i][j]==3)
                return 0;//impos
        }
    }
    vector<int> com;
    cnt=0;
    for(int i=0;i<n;i++)
        P[i]=-1;

    for(int i=0;i<n;i++)
    {
        if(C2[i]==0)cnt++;
        else continue;
        com.push_back(i);
        for(int j=0;j<n;j++)
        {
            if(p[i][j]==1)
            {
                P[j]=i;
                C2[j]=cnt;
            }
        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j)continue;
            if((p[i][j]==1)^(C2[i]==C2[j]))
                return 0;//impos
        }
    }

    for(int i=0;i<n;i++)
    {
        added(i,P[i]);
    }

    for(auto c:com)
    {
        vector<int> sub;
        if(vis[c])continue;
        for(auto s:com)
        {
            if(C1[c]==C1[s]&&!vis[s])
                sub.push_back(s);
        }

    for(auto s:sub)
        vis[s]=true;
    int siz=sub.size();
    if(siz==2)
        return 0;//impos
    if(siz>1)
    {
        for(int i=0;i<siz;i++)
            added(sub[i],sub[(i+1)%siz]);
    }
    }
    build(A);
    return 1;//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