Submission #1235876

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235876		stanirina	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	126 ms	26364 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

vector<vector<int>> g1;
vector<vector<int>> g2;
vector<bool> vis;
vector<int> col;
vector<vector<int>> cmp;
vector<vector<int>> cmp2;
vector<bool> pravicvor;

void dfs(int c,int color){
    if(vis[c])return;
    col[c]=color;
    vis[c]=true;
    for(auto a:g1[c]){
        if(vis[a])continue;
        dfs(a,color);
    }
}

void dfs2(int c,int color){
    if(vis[c])return;
    col[c]=color;
    vis[c]=true;
    for(auto a:g2[c]){
        if(vis[a])continue;
        dfs2(a,color);
    }
}
/*
void build(vector<vector<int>> ans){
    int n=ans.size();
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++)cout<<ans[i][j]<<' ';
    cout<<endl;
    }

}
*/
int construct(vector<vector<int>> p) {
	int n = p.size();
	vector<vector<int>> ans(n);
	for(int i=0;i<n;i++)ans[i].assign(n,0);

	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(p[i][j]==3)return 0;
        }
	}
    //cout<<"PRVA PROVERA"<<endl;
	g1.resize(n);
	for(int i=0;i<n;i++)g1[i].clear();
    vis.assign(n,false);
    col.assign(n,-1);
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(i==j)continue;
            if(p[i][j]==1)g1[i].push_back(j);
        }
	}

	for(int i=0;i<n;i++){
        if(col[i]!=-1)continue;
        vis.assign(n,false);
        dfs(i,i);
	}
	cmp.resize(n);
	for(int i=0;i<n;i++)cmp[i].clear();
	for(int i=0;i<n;i++)cmp[col[i]].push_back(i);

	for(int i=0;i<n;i++){                       //provera za jedinice
        for(int j=0;j<cmp[i].size();j++){
            for(int k=j+1;k<cmp[i].size();k++){
                if(p[cmp[i][j]][cmp[i][k]]!=1)return 0;
            }
        }
	}
	//cout<<"DRUGA PROVERA"<<endl;
	for(int i=0;i<n;i++){                       //provera za jedinice
        for(int j=1;j<cmp[i].size();j++){
            for(int k=0;k<n;k++){
                if(k==cmp[i][0] || k==cmp[i][j])continue;
                if(p[cmp[i][0]][k]!=p[cmp[i][j]][k])return 0;
            }
        }
	}
	//cout<<"TRECA PROVERA"<<endl;

	pravicvor.assign(n,false);        //poslednji deo drugog koraka
	for(int i=0;i<n;i++){
        if(cmp[i].size()==0)continue;
        pravicvor[cmp[i][0]]=true;
        for(int j=1;j<cmp[i].size();j++){
            ans[ cmp[i][0] ][ cmp[i][j] ]=1;
            ans[ cmp[i][j] ][ cmp[i][0] ]=1;
        }
	}

	///TRECI KORAK
    //cout<<"TRECI KORAK"<<endl;

	g2.resize(n);
	for(int i=0;i<n;i++)g2[i].clear();
    vis.assign(n,false);
    col.assign(n,-1);
	for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(!pravicvor[i])continue;
            if(!pravicvor[j])continue;
            if(p[i][j]==2)g2[i].push_back(j);
        }
	}
	for(int i=0;i<n;i++){
        if(col[i]!=-1)continue;
        if(!pravicvor[i])continue;
        vis.assign(n,false);
        dfs2(i,i);
	}
	//cout<<"ZAVRSEN DFS"<<endl;
	cmp2.resize(n);
	for(int i=0;i<n;i++)cmp2[i].clear();
	for(int i=0;i<n;i++){
	    if(col[i]==-1 || !pravicvor[i])continue;
        cmp2[col[i]].push_back(i);
	}

    for(int i=0;i<n;i++){
        for(int j=0;j<cmp2[i].size();j++){
            for(int k=j+1;k<cmp2[i].size();k++){
                if(p[cmp2[i][j]][cmp2[i][k]]!=2)return 0;
            }
        }
	}

	for(int i=0;i<n;i++){
        if(cmp2[i].size()==0 || cmp2[i].size()==1)continue;
        if(cmp2[i].size()<3)return 0;
        for(int j=0;j<cmp2[i].size()-1;j++){
            ans[ cmp2[i][j+1] ][ cmp2[i][j] ]=1;
            ans[ cmp2[i][j] ][ cmp2[i][j+1] ]=1;
        }
        ans[ cmp2[i][0] ][ cmp2[i][cmp2[i].size()-1] ]=1;
        ans[ cmp2[i][cmp2[i].size()-1] ][ cmp2[i][0] ]=1;

	}
	//cout<<"CETVRTA PROVERA"<<endl;

	build(ans);
	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