Submission #1186489

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186489		Warinchai	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	145 ms	26168 KiB

supertrees

#include "supertrees.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;

int N;
vector<vector<int>>adj;

int pa[1005];
int fp(int a){return pa[a]==a?a:pa[a]=fp(pa[a]);}
void un(int a,int b){pa[fp(b)]=fp(a);}

int have1[1005];
int have2[1005];
int have3[1005];

int vis1[1005];
int vis2[1005];
int vis3[1005];

int cant=0;

vector<vector<int>> answer;

void build1(int u){
    //cerr<<"build1:"<<u<<"\n";
    vector<int>node;
    node.push_back(u);
    vis1[u]=1;
    for(int i=0;i<N;i++)if(i!=u&&adj[u][i]==1){
        vis1[i]=1;
        node.push_back(i);
        un(i,u);
    }
    //for(auto x:node)cerr<<x<<" ";
    //cerr<<"\n";
    for(int i=0;i<node.size()-1;i++){
        int x=node[i],y=node[i+1];
        answer[x][y]=1,answer[y][x]=1;
    }
}

void build2(int u){
    //cerr<<"build2:"<<u<<"\n";
    vector<int>node;
    node.push_back(u);
    vis2[u]=1;
    for(int i=0;i<N;i++)if(i!=u&&adj[u][i]==2){
        vis2[i]=1;
        node.push_back(i);
    }
    if(node.size()<3)cant=1;
    for(int i=0;i<node.size();i++){
        int x=node[i],y=node[(i+1)%node.size()];
        answer[x][y]=1,answer[y][x]=1;
    }
}

void check_con(){
    /*for(int i=0;i<N;i++)pa[i]=i;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(adj[i][j]==1)un(i,j);
        }
    }
    for(int i=0;i<N;i++)for(int j=0;j<N;j++){
        if(i==j)continue;
        int x=(adj[i][j]==1);
        int y=(fp(i)==fp(j));
        if(x!=y)cant=1;
    }

    for(int i=0;i<N;i++)pa[i]=i;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(adj[i][j]==2)un(i,j);
        }
    }
    for(int i=0;i<N;i++)for(int j=0;j<N;j++){
        if(i==j)continue;
        int x=(adj[i][j]==2);
        int y=(fp(i)==fp(j));
        if(x!=y)cant=1;
    }

    for(int i=0;i<N;i++)pa[i]=i;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(adj[i][j]==3)un(i,j);
        }
    }
    for(int i=0;i<N;i++)for(int j=0;j<N;j++){
        if(i==j)continue;
        int x=(adj[i][j]==3);
        int y=(fp(i)==fp(j));
        if(x!=y)cant=1;
    }
    */
    for(int i=0;i<N;i++)pa[i]=i;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(adj[i][j]>0)un(i,j);
        }
    }
    for(int i=0;i<N;i++)for(int j=0;j<N;j++){
        if(i==j)continue;
        int x=(adj[i][j]>0);
        int y=(fp(i)==fp(j));
        if(x!=y)cant=1;
    }
}

int construct(std::vector<std::vector<int>> p) {
	N = p.size();
	for (int i = 0; i < N; i++) {
		vector<int> row;
		row.resize(N);
		answer.push_back(row);
	}
	adj=p;
    for(int i=0;i<N;i++)pa[i]=0;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int x=p[i][j];
            if(x==1)have1[i]=1;
            else if(x==2)have2[i]=1;
            else if(x==3)have3[i]=1;
        }
    }
    for(int i=0;i<N;i++)for(int j=0;j<N;j++)if(adj[i][j]!=adj[j][i])cant=1;
    for(int i=0;i<N;i++)if(have1[i]&&vis1[i]==0)build1(i);
    for(int i=0;i<N;i++)pa[i]=0;
    for(int i=0;i<N;i++){
        int x=fp(i);
        if(have2[x]&&vis2[x]==0)build2(x);
    }
    check_con();
    if(cant)return 0;
    build(answer);
    return 1;
}

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