Submission #1050037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050037		AlperenT_	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	171 ms	40808 KiB

supertrees

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

#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define ld long double 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2000 + 10  , sq = 333   , inf = 2e9 +100 , maxk = 2022 , mod = 1e9 + 7 ;
int n , ok =1 , cnt2 = 1 ,  cnt = 1  , mark[maxn] ,p[maxn][maxn] , b[maxn][maxn]  , c[maxn] , ye[maxn] , c2[maxn] ;
vector <int> vec ;

void dfs(int v){
    vec.pb(v) ;
    c[v] = cnt ; 
    mark[v] =1 ; 
    rep(j , 0 ,n-1){
        if(mark[j]==0 && p[v][j]){
            dfs(j) ; 
        }
    }
}
vector <int> vec2 ; 
void dfs2(int v){
    mark[v] =1 ;
    c2[v] = cnt2 ; 
    ye[cnt2] = v;  
    for(int u :  vec2){
        if(mark[u]==1 || p[v][u] == 2)continue ; 
        dfs2(u) ;
    }
}
void add(int x ,int y){
    b[x][y] = b[y][x] =1 ;
}

bool ch(vector <int> vec){
    vec2 = vec ;
    cnt2 = 1 ;
    for(int x : vec)mark[x] =0 ;
    for(int x : vec){
        if(mark[x] == 1)continue ;
        dfs2(x) ;
        cnt2++ ;
    }
    cnt2--;
    for(int x : vec){
        for(int y : vec){
            if(c2[x] == c2[y] && p[x][y] == 2)return 0 ;
        }
    }
    rep(i , 1 ,cnt2){
        vector <int> az ;
        for(int x : vec){
            if(c2[x] == i)az.pb(x);
        }
        rep(j ,1 ,sz(az)-1)add(az[j-1],az[j]) ;
    }
    if(cnt2==1)return 1 ; 
    if(cnt2 == 2){
        if(sz(vec)==2)return 0 ;
        vector <int> a[2] ;
        for(int v : vec){
            a[c2[v]-1].pb(v) ;
        }   
        if(sz(a[0]) > sz(a[1]))swap(a[0] , a[1]) ;
        add(a[0][0] , a[1][0]) ;
        add(a[0][0] , a[1][1]) ; 
        return 1 ;
    }
    add(ye[1],ye[cnt2]) ;
    rep(i ,2 , cnt2){
        add(ye[i-1] , ye[i]);
    }
    return 1 ;
}

int construct(vector<std::vector<int>> pp) {
    n = sz(pp);
    rep(i , 0 , n-1){
        rep(j , 0 ,n-1){
            p[i][j] = pp[i][j] ;
            if(p[i][j] == 3)return 0 ;
        }
    }
    rep(i ,0 , n-1){
        if(mark[i] == 1)continue ; 
        dfs(i) ;
        cnt++;
    }
    cnt--;
    rep(i ,0  ,n-1){
        rep(j , 0 ,n-1){
            if((c[i]==c[j] && p[i][j]==0) || (c[i]!=c[j] && p[i][j]>0))return 0 ;
        }
    }
    rep(i , 1, cnt){
        vector <int> vec;
        rep(j , 0 , n-1){
            if(c[j] == i){
                vec.pb(j) ;
            }
        }
        if(ch(vec)==0)return 0 ;
    }
    vector <vector <int> > bb ;
    rep(i , 0 , n-1){
        vector <int> f ;
        rep(j , 0, n-1){
            f.pb(b[i][j]) ;
        }
        bb.pb(f) ;
    }
    build(bb) ;
    return 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