Submission #300806

#	Time	Username	Problem	Language	Result	Execution time	Memory
300806		ainta	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	258 ms	22396 KiB

supertrees

#include "supertrees.h"
#include <vector>
using namespace std;

int Num[1010], Num2[1010], PPP[1010], vis[1010];

vector<vector<int>>E;
void Add(int a, int b){
    if(a==-1||b==-1||a==b)return;
    E[a][b]=E[b][a]=1;
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
    int i, j, cnt = 0;
    E.resize(n);
    for(i=0;i<n;i++){
        E[i].resize(n);
        for(j=0;j<n;j++){
            E[i][j]=0;
        }
    }
    for(i=0;i<n;i++){
        if(!Num[i])cnt++;
        else continue;
        for(j=0;j<n;j++){
            if(p[i][j]){
                Num[j]=cnt;
            }
        }
    }
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if((Num[i]==Num[j])!=(p[i][j]!=0))return 0;
            if(p[i][j]==3)return 0;
        }
    }
    int cc=0;
    for(i=0;i<n;i++)PPP[i]=-1;


    vector<int>T;
    for(i=0;i<n;i++){
        if(!Num2[i])cc++;
        else continue;
        T.push_back(i);
        for(j=0;j<n;j++){
            if(p[i][j]==1){
                Num2[j]=cc;
                PPP[j]=i;
            }
        }
    }


    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            if(i==j)continue;
            if((Num2[i]==Num2[j])!=(p[i][j]==1))return 0;
        }
    }
    for(i=0;i<n;i++){
        Add(i,PPP[i]);
    }

    for(auto &t : T){
        vector<int>Z;
        if(vis[t])continue;
        for(auto &x : T){
            if(!vis[x] && Num[t]==Num[x]){
                Z.push_back(x);
            }
        }
        for(auto &x : Z)vis[x]=1;
        int sz = Z.size();
        if(sz==2){
            return 0;
        }
        if(sz>1){
            for(i=0;i<sz;i++){
                Add(Z[i],Z[(i+1)%sz]);
            }
        }
    }

    build(E);

	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