Submission #457578

#	Time	Username	Problem	Language	Result	Execution time	Memory
457578		vector	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	277 ms	24132 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define SIZE 1001
using namespace std;
int root[SIZE], a[SIZE];
vector<vector<int> > con;
vector<vector<vector<int> > > lin;
int Find(int x)
{
    if (x==root[x]) return x;
    return root[x]=Find(root[x]);
}
void Union(int x, int y)
{
    if (Find(x)==Find(y)) return;
    root[root[x]]=root[y];
}
int construct(vector<vector<int> > p)
{
	int N=p.size(), M;
	vector<vector<int> > ret(N);
	for (int i=0; i<N; i++) {
        ret[i].resize(N);
        root[i]=i, a[i]=-1;
	}
	for (int i=0; i<N; i++) for (int j=0; j<N; j++) if (i!=j) {
        if (p[i][j]==3) return 0;
        if (p[i][j]!=0) Union(i, j);
	}
	for (int i=0; i<N; i++) {
        if (a[Find(i)]==-1) {
            a[root[i]]=con.size();
            vector<int> v;
            v.push_back(i);
            con.push_back(v);
        }
        else con[a[root[i]]].push_back(i);
	}
	M=con.size();
	lin.resize(M);
	for (int i=0; i<M; i++) for (int j : con[i]) for (int k : con[i]) if (p[j][k]==0) return 0;
	for (int i=0; i<N; i++) root[i]=i, a[i]=-1;
	for (int i=0; i<M; i++) {
        for (int j : con[i]) for (int k : con[i]) if (j!=k && p[j][k]==1) Union(j, k);
        for (int j : con[i]) {
            if (a[Find(j)]==-1) {
                a[root[j]]=lin[i].size();
                vector<int> v;
                v.push_back(j);
                lin[i].push_back(v);
            }
            else lin[i][a[root[j]]].push_back(j);
        }
        if (lin[i].size()==2) return 0;
        for (int j=0; j<lin[i].size(); j++) for (int k : lin[i][j]) for (int l : lin[i][j]) if (p[k][l]==2) return 0;
        for (int j=0; j<lin[i].size(); j++) for (int k=0; k<lin[i][j].size(); k++) {
            if (k!=0) ret[lin[i][j][k]][lin[i][j][k-1]]=1;
            if (k!=lin[i][j].size()-1) ret[lin[i][j][k]][lin[i][j][k+1]]=1;
        }
        for (int j=0; j<lin[i].size()-1; j++) ret[lin[i][j][0]][lin[i][j+1][0]]=ret[lin[i][j+1][0]][lin[i][j][0]]=1;
        if (lin[i].size()>1) {
            ret[lin[i][lin[i].size()-1][0]][lin[i][0][0]]=1;
            ret[lin[i][0][0]][lin[i][lin[i].size()-1][0]]=1;
        }
	}
	build(ret);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:55:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         for (int j=0; j<lin[i].size(); j++) for (int k : lin[i][j]) for (int l : lin[i][j]) if (p[k][l]==2) return 0;
      |                       ~^~~~~~~~~~~~~~
supertrees.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j=0; j<lin[i].size(); j++) for (int k=0; k<lin[i][j].size(); k++) {
      |                       ~^~~~~~~~~~~~~~
supertrees.cpp:56:60: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j=0; j<lin[i].size(); j++) for (int k=0; k<lin[i][j].size(); k++) {
      |                                                           ~^~~~~~~~~~~~~~~~~
supertrees.cpp:58:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if (k!=lin[i][j].size()-1) ret[lin[i][j][k]][lin[i][j][k+1]]=1;
      |                 ~^~~~~~~~~~~~~~~~~~~~
supertrees.cpp:60:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int j=0; j<lin[i].size()-1; j++) ret[lin[i][j][0]][lin[i][j+1][0]]=ret[lin[i][j+1][0]][lin[i][j][0]]=1;
      |                       ~^~~~~~~~~~~~~~~~

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