Submission #300579

#	Time	Username	Problem	Language	Result	Execution time	Memory
300579		muhammad_hokimiyon	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	288 ms	26232 KiB

supertrees

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

using namespace std;

const int maxn = 1010;

bool used[maxn];
vector < int > v[maxn],c;

void dfs( int x )
{
    if( used[x] )return;
    used[x] = true;
    c.push_back(x);
    for( auto y : v[x] ){
        dfs( y );
    }
}

int construct( vector<vector<int>> p )
{
    int n = (int)p.size();
    for( int i = 0; i < n; i++ ){
        if( p[i][i] != 1 )return 0;
        for( int j = 0; j < n; j++ ){
            if( p[i][j] == 3 || p[i][j] != p[j][i] )return 0;
            if( p[i][j] == 0 )continue;
            if( p[i][j] == 1 ){
                v[i].push_back(j);
            }
        }
    }
    vector < vector < int > > ans( n , vector < int > (n , 0) );
    vector < int > fg;
    vector < vector < int > > gr(n);
    for( int it = 0; it < n; it++ ){
        if( used[it] )continue;
        c.clear();
        dfs( it );
        fg.push_back(it);
        gr[it] = c;
        int sz = (int)c.size();
        int cnt1 = 0 , cnt2 = 0;
        vector < int > ch( n , 0 );
        for( int i = 0; i < sz; i++ ){
            ch[c[i]] = 1;
            for( int j = 0; j < sz; j++ ){
                int x = c[i] , y = c[j];
                if( p[x][y] != 1 ){
                    return 0;
                }
            }
            if( i + 1 < sz ){
                int x = c[i] , y = c[i + 1];
                ans[x][y] = ans[y][x] = 1;
            }
        }
        for( int i = 0; i < sz; i++ ){
            for( int j = 0; j < n; j++ ){
                int x = c[i] , y = j;
                if( ch[y] )continue;
                cnt1 += 1;
                if( p[x][y] == 0 )cnt2 += 1;
            }
        }
        if( cnt2 == cnt1 ){
            fg.pop_back();
        }
    }
    for( int i = 0; i < (int)fg.size(); i++ ){
        int cnt = 0;
        for( auto x : gr[fg[i]] ){
            for( int j = 0; j < (int)fg.size(); j++ ){
                if( i == j )continue;
                for( auto y : gr[fg[j]] ){
                    if( p[x][y] == 1 )cnt += 1;
                }
            }
        }
        if( cnt > 0 )return 0;
    }
    for( int i = 0; i < n; i++ ){
        used[i] = false;
        v[i].clear();
        for( int j = 0; j < n; j++ ){
            if( p[i][j] != 0 ){
                v[i].push_back(j);
            }
        }
    }
    for( int i = 0; i < n; i++ ){
        if( used[i] )continue;
        c.clear();
        dfs( i );
        int sz = (int)c.size();
        for( int j = 0; j < sz; j++ ){
            for( int h = 0; h < sz; h++ ){
                int x = c[j] , y = c[h];
                if( p[x][y] == 0 ){
                    return 0;
                }
            }
        }
    }
    if( !fg.empty() && (int)fg.size() < 3 )return 0;
    for( int i = 0; i + 1 < (int)fg.size(); i++ ){
        int x = fg[i] , y = fg[i + 1];
        ans[x][y] = ans[y][x] = 1;
    }
    if( !fg.empty() ){
        int x = fg[0] , y = fg.back();
        ans[x][y] = ans[y][x] = 1;
    }
    build( ans );
    return 1;
}

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