Submission #1014680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014680		Unforgettablepl	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	140 ms	24184 KiB

supertrees

#include <bits/stdc++.h>
using namespace std;

void build(std::vector<std::vector<int>> b);

int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    vector<vector<vector<int>>> components;
    vector<int> componentstype;
    for(int i=0;i<n;i++){
        int mycomponent = -1;
        for(int compo=0;compo<components.size();compo++){
            int shouldbe = p[i][components[compo][0][0]];
            shouldbe = min(shouldbe,1);
            if(shouldbe==1){
                if(mycomponent==-1)mycomponent=compo;
                else return 0;
            }
            for(auto&j:components[compo]){
                for(int&k:j){
                    if(shouldbe==0 and p[i][k]!=0)return 0;
                    if(shouldbe==1 and p[i][k]==0)return 0;
                }
            }
        }
        if(mycomponent==-1){
            components.push_back({{i}});
            componentstype.push_back(-1);
            continue;
        }
        int mychain = -1;
        for(int cha=0;cha<components[mycomponent].size();cha++){
            int shouldbe = p[i][components[mycomponent][cha][0]];
            if(shouldbe==1){
                if(mychain==-1)mychain=cha;
                else return 0;
            } else {
                if(componentstype[mycomponent]==-1)componentstype[mycomponent]=shouldbe;
                else if(componentstype[mycomponent]!=shouldbe)return 0;
            }
            for(int&j:components[mycomponent][cha]){
                if(shouldbe!=p[i][j])return 0;
            }
        }
        if(mychain==-1)components[mycomponent].push_back({i});
        else components[mycomponent][mychain].push_back(i);
    }
    vector<vector<int>> ans(n,vector<int>(n));
    for(int i=0;i<components.size();i++){
        vector<int> heads;
        for(auto&j:components[i]){
            heads.emplace_back(j[0]);
            for(int k=1;k<j.size();k++){
                ans[j[k-1]][j[k]]=ans[j[k]][j[k-1]]=true;
            }
        }
        if(heads.size()==2)return 0;
        if(heads.size()==1)continue;
        if(componentstype[i]==3)return 0;
        heads.emplace_back(heads.front());
        for(int j=1;j<heads.size();j++){
            ans[heads[j-1]][heads[j]]=ans[heads[j]][heads[j-1]]=true;
        }
        if(componentstype[i]==3)ans[heads[0]][heads[2]]=ans[heads[2]][heads[0]]=true;    
    }
    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:12:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |         for(int compo=0;compo<components.size();compo++){
      |                         ~~~~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int cha=0;cha<components[mycomponent].size();cha++){
      |                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for(int i=0;i<components.size();i++){
      |                 ~^~~~~~~~~~~~~~~~~~
supertrees.cpp:53:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int k=1;k<j.size();k++){
      |                         ~^~~~~~~~~
supertrees.cpp:61:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |         for(int j=1;j<heads.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