Submission #697684

#	Time	Username	Problem	Language	Result	Execution time	Memory
697684		DJeniUp	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	177 ms	22160 KiB

supertrees

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

using namespace std;

typedef long long ll;
typedef pair<ll,ll>pairll;

#define pb push_back
#define fr first
#define sc second
#define INF 10000000007

vector<vector<int> >ans;

ll h,f[1007],pr[1007],k[1007];

vector<ll>v[1007];

ll A(ll x){
    if(pr[x]!=x)pr[x]=A(pr[x]);
    return pr[x];
}

void S(ll x,ll y){
    if(rand()%2==0)swap(x,y);
    pr[A(x)]=A(y);
    return ;
}

int construct(std::vector<std::vector<int>> p) {
	ll n = p.size();
    
	for (int i = 0; i < n; i++) {
        pr[i]=i;
		std::vector<int> row;
		row.resize(n);
		ans.pb(row);
	}
    for(int i=0;i<n;i++){
        if(f[i]==0){
            for(int j=0;j<i;j++){
                if(p[i][j]==1){
                    ans[i][j]=1;
                    ans[j][i]=1;
                    S(i,j);
                    break;
                }
            }
        }
    }
    for(int i=0;i<n;i++){
        for(int j=1;j<=h;j++){
            ll fl=0;
            for(auto it:v[j]){
                if(p[i][it]!=2)fl=1;
            }
            if(f[i]==2 && fl==0 && A(i)!=A(v[j][0]))return 0;
            if(fl==0 && A(i)!=A(v[j][0])){
                //cout<<i<<" "<<j<<endl;
                S(i,v[j][0]);
                v[j].pb(i);
                f[i]=2;
            }
        }
        if(f[i]!=2){
            for(int j=0;j<i;j++){
                if(p[i][j]==2 && A(i)!=A(j)){
                    
                    h++;
                    S(i,j);
                    //cout<<i<<" "<<h<<endl;
                    //cout<<j<<" "<<h<<endl;
                    f[i]=2;
                    f[j]=2;
                    v[h].pb(i);
                    v[h].pb(j);
                    break;
                }
            }
        }
    }
    //cout<<1<<endl;
    for(int i=0;i<n;i++){
        if(f[i]==0){
            for(int j=0;j<n;j++){
                if(p[i][j]==1 && f[j]==2){
                    f[i]=3;
                    k[i]=j;
                    break;
                }
            }
        }
    }
    //for(int i=0;i<n;i++)cout<<f[i]<<" ";
    //cout<<endl;
    
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j]==0){
                if(A(j)==A(i))return 0;
            }
            if(p[i][j]==1){
                if(f[i]==3 && f[j]==3 && k[i]==k[j])continue;
                else if(f[i]==2 && f[j]==3 && i==k[j])continue;
                else if(f[i]==3 && f[j]==2 && j==k[i])continue;
                else if(f[i]==0 && f[j]==0 && A(i)==A(j))continue;
                else return 0;
            }
            if(p[i][j]==2){
                if(f[i]==2 && f[j]==2 && A(i)==A(j))continue;
                else if(f[i]==2 && f[j]==3 && k[j]!=i)continue;
                else if(f[i]==3 && f[j]==2 && k[i]!=j)continue;
                else if(f[i]==3 && f[j]==3 && k[i]!=k[j])continue;
                else return 0;
            }
            if(p[i][j]==3)return 0;
        }
    }
    //cout<<2<<endl;
    for(int i=1;i<=h;i++){
        if(v[i].size()<=2)return 0;
        for(int j=1;j<v[i].size();j++){
            ans[v[i][j]][v[i][j-1]]=1;
            ans[v[i][j-1]][v[i][j]]=1;
        }
        ans[v[i][v[i].size()-1]][v[i][0]]=1;
        ans[v[i][0]][v[i][v[i].size()-1]]=1;
    }
    //cout<<3<<endl;
	build(ans);
	return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int j=1;j<v[i].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