Submission #928173

#	Time	Username	Problem	Language	Result	Execution time	Memory
928173		AlphaMale06	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	188 ms	23624 KiB

supertrees

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

using namespace std;

#define pb push_back

void check(bool cond, string message);
void build(vector<vector<int>> _b);

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]!=0)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]==0 && 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())continue;
        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;
        int cnt=1;
        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]){
                cnt++;
                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;
            }
        }
        if(cnt==2 && p[cmp[0]][cmp[1]]==2)return 0;
    }
    build(answer);
	return 1;
}

Compilation message (stderr)

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

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