Submission #309475

#	Time	Username	Problem	Language	Result	Execution time	Memory
309475		pere_gil	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	256 KiB

supertrees

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

using namespace std;

int pos[1001];

void init(int n){
    for(int i=0;i<n;i++) pos[i]=i;
}

int findset(int a){
    if(pos[a]==a) return a;
    else return pos[a]=findset(pos[a]);
}

void unionset(int A, int B){
    int a=findset(A);
    int b=findset(B);
    if(a!=b) pos[b]=a;
}

bool issameset(int a, int b){
    if(findset(a)==findset(b)) return true;
    else return false;
}

int construct(std::vector<std::vector<int> > p)
{
    int n = p.size();
    std::vector<std::vector<int> > answer;
    init(n);

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

    vector<int> ja[n];
    for(int i=0;i<n;i++) ja[findset(i)].push_back(i);

    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(issameset(i,j) && p[i][j]==0) return 0;
            if(!issameset(i,j) && p[i][j]!=0) return 0;
            if(i==j && p[i][j]!=1) return 0;   /// semamo
        }
    }

    int res[n+1][n+1];
    memset(res,0,sizeof(res));
    for(int i=0;i<n;i++){
        for(int j=1;j<ja[i].size();j++){
            res[ ja[i][j] ]   [ ja[i][j-1] ]=1;
            res[ ja[i][j-1] ] [ ja[i][j] ]=1;
        }
        if(ja[i].size()>1){
        res[ja[i][0]] [ ja[i][ja[i].size()-1] ]=1;
        res[ja[i][ja[i].size()-1]] [ja[i][0]]=1;
        }
    }

    for (int i = 0; i < n; i++) {
        std::vector<int> row;
        for(int j=0;j<n;j++) row.push_back(res[i][j]);
        row.resize(n);
        answer.push_back(row);
    }

    build(answer);
    return 1;
}

Compilation message (stderr)

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

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