Submission #343121

#	Time	Username	Problem	Language	Result	Execution time	Memory
343121		bigDuck	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	282 ms	26092 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
#define INIT  ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define ll long long
#define pii pair<int, int>
#define count_bits __builtin_popcount


vector<pii> c1;
vector<pii> c2;
vector<int> c3;
vector<vector<int> > P;
int N;
int r[1010][4];
vector<vector<int>> B;

void b1(){

for(int i=0; i<N; i++){
    if(r[i][1]==(-1)){
        r[i][1]=i;
        int mx=i;
        for(int j=0; j<N; j++){
            if( (P[i][j]==1) && (i!=j) ){
                B[mx][j]=1;
                B[j][mx]=1;
                r[j][1]=i;
                mx=j;
            }
        }
        c1.pb({i, mx});
    }
}


}


void b2(){
    for(pii p1:c1){
        int u1=p1.ft, v1=p1.sc;

        if(r[u1][2]==(-1)){
            c2.pb({u1, u1});
            int mx=u1;
            for(pii p2:c1){
                int u2=p2.ft, v2=p2.sc;
                if(u2==u1){continue;}

                if( (r[ r[u2][1] ][2]==(-1)) && (P[u1][u2]==2)  ){
                    B[mx][u2]=1;
                    B[u2][mx]=1;
                    r[u1][2]=u1;
                    r[u2][2]=u1;
                    mx=u2;
                    c2.back()={v1, v2};
                }
            }
            if( (c2[c2.size()-1])==mp(u1, u1) ){
                c2.pop_back();
            }
            else{
                B[u1][mx]=1;
                B[mx][u1]=1;
            }
        }

    }
}



bool check(){

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            if(P[i][j]==3){
                return false;
            }
            if( (r[i][1]==r[j][1]) && (P[i][j]!=1) ){
                return false;
            }
            if( (r[i][1]!=r[j][1]) && (P[i][j]==1) ){
                return false;
            }
            if( (P[i][j]==2) && ( (r[ r[i][1] ][2]!=r[ r[j][1] ][2]) || (r[ r[i][1] ][2]==(-1)) ) ){
                return false;
            }
            if( (r[ r[i][1] ][2]==r[ r[j][1] ][2]) && (r[ r[i][1] ][2]!=(-1)) && (r[i][1]!=r[j][1]) && (P[i][j]!=2) ){
                return false;
            }
        }
    }
    return true;
}


int construct(std::vector<std::vector<int>> p) {
P=p; N=P.size();
memset(r, -1, sizeof(r));

B.resize(N);
for(int i=0; i<N; i++){
    B[i].resize(N);
    for(int j=0; j<N; j++){
        B[i][j]=0;
    }
}

b1();
b2();


if(check()){
    build(B);
    return 1;
}
return 0;
}

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