Submission #631784

#	Time	Username	Problem	Language	Result	Execution time	Memory
631784		PoonYaPat	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	247 ms	25036 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
 
int head[1001],hc[1001];
bool ans[1001][1001];
vector<int> cycle[1001];
 
int construct(vector<vector<int>> p) {
 
	int n = p.size();
	vector<vector<int>> answer;
	memset(head,-1,sizeof(head));
	memset(hc,-1,sizeof(hc));
 
	//create tree
	for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            if (p[i][j]==1) {
 
                if (head[i]!=-1 && head[j]!=-1) {
                    if (head[i]!=head[j]) return 0;
                }
                else if (head[i]!=-1) head[j]=head[i], ans[head[i]][j]=ans[j][head[i]]=true;
                else if (head[j]!=-1) head[i]=head[j], ans[head[j]][i]=ans[i][head[j]]=true;
                else {
                    head[i]=i; head[j]=i; ans[i][j]=ans[j][i]=true;
                }
            }
        }
	}
	for (int i=0; i<n; ++i) {
        if (head[i]==-1) head[i]=i;
	}
 
    //create cycle
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            if (p[i][j]!=1 && head[i]==head[j] && head[i]!=-1) return 0;
            if (p[i][j]==2) {
                int x=head[i], y=head[j];
 
                if (hc[x]!=-1 && hc[y]!=-1) {
                    if (hc[x]!=hc[y]) return 0;
                }
                else if (hc[x]!=-1) hc[y]=hc[x], cycle[hc[x]].push_back(y);
                else if (hc[y]!=-1) hc[x]=hc[y], cycle[hc[y]].push_back(x);
                else {
                    hc[i]=i; hc[j]=i;
                    cycle[i].push_back(i);
                    cycle[i].push_back(j);
                }
            }
        }
	}
 
	for (int i=0; i<n; ++i) {
        if (cycle[i].size()) {
          	if (cycle[i].size()==2) return 0;
            for (int j=1; j<cycle[i].size(); ++j) ans[cycle[i][j]][cycle[i][j-1]]=ans[cycle[i][j-1]][cycle[i][j]]=true;
            ans[cycle[i][cycle[i].size()-1]][cycle[i][0]]=ans[cycle[i][0]][cycle[i][cycle[i].size()-1]]=true;
        }
	}
 
	//check component
	for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            if (p[i][j]==3) return 0;
            if (p[i][j]==0 && hc[head[i]]==hc[head[j]] && hc[head[i]]!=-1) return 0;
        }
	}
 
	for (int i=0; i<n; ++i) {
        vector<int> row;
        for (int j=0; j<n; ++j) row.push_back(ans[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:60:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for (int j=1; j<cycle[i].size(); ++j) ans[cycle[i][j]][cycle[i][j-1]]=ans[cycle[i][j-1]][cycle[i][j]]=true;
      |                           ~^~~~~~~~~~~~~~~~

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