Submission #522462

#	Time	Username	Problem	Language	Result	Execution time	Memory
522462		krit3379	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	201 ms	26948 KiB

supertrees

#include<bits/stdc++.h>
using namespace std;
#include "supertrees.h"
#define N 1005

int p[N],pp[N];
vector<int> v;
vector<vector<int>> a,b;
bitset<N> vis,ch;

int fp(int v){return (v==p[v])?v:p[v]=fp(p[v]);}
int fpp(int v){return (v==pp[v])?v:pp[v]=fpp(pp[v]);}

bool sol(int n){
    int i,j,cy=0,head,num;
    vector<int> gr[N],u;
    ch=0;
    iota(pp,pp+n,0);
    for(i=0;i<n;i++){
        for(j=0;j<n;j++){
            num=a[v[i]][v[j]];
            if(num==1){
                if(fpp(i)!=fpp(j))pp[fpp(i)]=fpp(j);
            }
            else if(!cy){
                cy=num;
            }
            else if(cy!=num)return false;

        }
    }
    for(i=0;i<n;i++)gr[fpp(i)].push_back(v[i]);
    if(!cy){
        for(i=1;i<n;i++)b[v[i]][v[i-1]]=b[v[i-1]][v[i]]=1;
        return true;
    }
    else{
        for(i=0;i<n;i++){
            if(ch[fpp(i)])continue;
            head=fpp(i);
            u.push_back(v[head]);
            ch[head]=true;
            for(auto x:gr[head]){
                for(j=0;j<n;j++){
                    if(fpp(j)==head){
                        if(a[x][v[j]]!=1)return false;
                    }
                    else{
                        if(a[x][v[j]]!=cy)return false;
                    }
                }
            }
        }
        for(i=0;i<n;i++)
            for(j=1;j<gr[i].size();j++)b[gr[i][j]][gr[i][j-1]]=b[gr[i][j-1]][gr[i][j]]=1;
        if(u.size()<3)return false;
        for(i=1;i<u.size();i++)b[u[i]][u[i-1]]=b[u[i-1]][u[i]]=1;
        b[u[0]][u.back()]=b[u.back()][u[0]]=1;
        return true;
    }
}

int construct(vector<vector<int>> input) {
    a=input;
	int n=a.size(),i,j,m;
	bool flag;
	iota(p,p+n,0);
	for(i=0;i<n;i++){
        b.push_back({});
        b[i].resize(n);
        for(j=0;j<n;j++){
          	if(a[i][j]==3)return 0;
            if(a[i][j]){
                if(fp(i)==fp(j))continue;
                p[fp(i)]=fp(j);
            }
            else if(fp(i)==fp(j))return 0;
        }
	}
	for(i=0;i<n;i++){
        if(!vis[fp(i)]){
            vis[fp(i)]=true;
            for(j=0;j<n;j++)if(fp(i)==fp(j))v.push_back(j);
            m=v.size();
            flag=sol(m);
            v.clear();
            if(!flag)return 0;
        }
	}
	build(b);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'bool sol(int)':
supertrees.cpp:55:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(j=1;j<gr[i].size();j++)b[gr[i][j]][gr[i][j-1]]=b[gr[i][j-1]][gr[i][j]]=1;
      |                     ~^~~~~~~~~~~~~
supertrees.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |         for(i=1;i<u.size();i++)b[u[i]][u[i-1]]=b[u[i-1]][u[i]]=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