Submission #928172

#	Time	Username	Problem	Language	Result	Execution time	Memory
928172		AlphaMale06	Connecting Supertrees (IOI20_supertrees)	C++17	56 / 100	181 ms	23704 KiB

supertrees

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

using namespace std;

#define pb push_back

const int N = 1005;
int par[N];
int sz[N];
vector<int> comp[N];
vector<vector<int>> answer;

void make(int v){
    par[v]=v;
    sz[v]=1;
}

int find(int v){
    if(par[v]==v)return v;
    return par[v]=find(par[v]);
}

void merge(int u, int v){
    u=find(u);
    v=find(v);
    if(u==v)return;
    if(sz[u]<sz[v])swap(u, v);
    sz[u]+=sz[v];
    par[v]=u;
}

int construct(vector<vector<int>> p) {
	int n = p.size();
	answer.resize(n);
	for(int i=0; i<n; i++){
        answer[i].resize(n);
        for(int j=0; j<n; j++)answer[i][j]=0;
	}
    for(int i=0; i<n; i++)make(i);
    for(int i=0; i< n; i++){
        for(int j=0; j< n; j++){
            if(p[i][j])merge(i, j);
            if(p[i][j]==3)return 0;
        }
    }
    for(int i=0; i< n; i++){
        for(int j=0; j< n; j++){
            if(!p[i][j]){
                if(find(i)==find(j))return 0;
            }
        }
    }
    for(int i=0; i< n; i++){
        comp[find(i)].pb(i);
    }
    for(int i=0; i < n; i++)make(i);
    for(vector<int> cmp : comp){
        if(cmp.size()){
            for(int e : cmp){
                for(int i : cmp){
                    if(p[e][i]==1){
                        merge(e, i);
                    }
                }
            }
            for(int e : cmp){
                for(int i : cmp){
                    if(p[e][i]==2 && find(e)==find(i))return 0;
                }
            }
            for(int e : cmp){
                int f=find(e);
                if(f!=e){
                    answer[e][f]=1;
                    answer[f][e]=1;
                }
            }
            vector<int> vc;
            for(int e : cmp)vc.pb(find(e));
            sort(vc.begin(), vc.end());
            for(int i=1; i<vc.size(); i++){
                if(vc[i]!=vc[i-1]){
                    answer[vc[i]][vc[i-1]]=1;
                    answer[vc[i-1]][vc[i]]=1;
                }
                if(vc.back()!=vc[0]){
                    answer[vc.back()][vc[0]]=1;
                    answer[vc[0]][vc.back()]=1;
                }
            }
        }
    }
    build(answer);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             for(int i=1; i<vc.size(); i++){
      |                          ~^~~~~~~~~~

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