Submission #306865

#	Time	Username	Problem	Language	Result	Execution time	Memory
306865		knon0501	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	258 ms	22392 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
const int MX=1e3+5;
int pr[MX];
int pp[MX];
vector<int> a[MX];
vector<int> b[MX];

int f(int x){
    return x==pr[x] ? x:pr[x]=f(pr[x]);
}
void U(int x,int y){
    int xx=f(x);
    int yy=f(y);
    if(xx==yy)return;
    if(a[xx].size()>a[yy].size())swap(xx,yy);
    pr[xx]=yy;
    for(auto k: a[xx])a[yy].push_back(k);
}
int g(int x){
    return x==pp[x] ? x:pp[x]=g(pp[x]);
}
void U2(int x,int y){
    int xx=g(x);
    int yy=g(y);
    if(xx==yy)return;
    if(b[xx].size()>b[yy].size())swap(xx,yy);
    pp[xx]=yy;
    for(auto k: b[xx])b[yy].push_back(k);
}
int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	std::vector<std::vector<int>> answer(n);
    int i,j;
    for(i=0 ; i<n ; i++){
        pr[i]=i;
        pp[i]=i;
        a[i].push_back(i);
        b[i].push_back(i);
    }

	for(i=0 ; i<n ; i++){
        answer[i].resize(n);
        for(j=i+1 ; j<n ; j++){
            if(p[i][j]==3)return 0;
            if(p[i][j]==1){
                U(i,j);
            }
        }
	}

	for(i=0 ; i<n ; i++){
        if(i==f(i)){
            for(auto x: a[f(i)]){
                for(auto y: a[f(i)]){
                    if(p[x][y]!=1)return 0;
                }
            }
            for(j=1 ; j<a[f(i)].size() ; j++){
                answer[a[f(i)][j]][a[f(i)][j-1]]=answer[a[f(i)][j-1]][a[f(i)][j]]=1;
            }
        }
	}

	for(int i=0 ; i<n ; i++){
        for(int j=i+1 ; j<n ; j++){
            if(p[i][j]==2){
                U2(f(i),f(j));
            }
        }
	}

	for(i=0 ; i<n ; i++){
        if(g(i)!=i)continue;
        int s=b[i].size();
        if(s==1)continue;
        if(s==2)return 0;
        for(j=0 ; j<s ; j++){
            for(int k=j+1 ; k<s ; k++){
                for(auto x: a[b[i][j]])
                    for(auto y: a[b[i][k]])
                        if(p[x][y]!=2)
                            return 0;
            }

        }
        for(j=0 ; j<s ; j++){
            answer[b[i][j]][b[i][(j+1)%s]]=answer[b[i][(j+1)%s]][b[i][j]]=1;
        }
	}
	build(answer);
	return 1;
}

Compilation message (stderr)

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

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