Submission #1031339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031339		hotboy2703	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	149 ms	24148 KiB

supertrees

#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL<<(i))
namespace trung{
    const ll MAXN = 1510;
    ll a[MAXN][MAXN];
    bool in[MAXN];
    ll cnt2[MAXN];
    ll n;
}
int construct(std::vector<std::vector<int>> b){
    using namespace trung;
    n=sz(b);
    for (ll i = 0;i < n;i ++)for (ll j = 0;j < n;j ++){
        if (b[i][j] == 3)return 0;
        cnt2[i] += b[i][j] == 2;
    }
    vector <vector <ll> > res(n,vector <ll> (n));
    for (ll i = 0;i < n;i ++){
        if (in[i]==0){
            queue <ll> q;
            q.push(i);
            in[i] = 1;
            vector <ll> all;
            while (!q.empty()){
                ll u = q.front();
                all.push_back(u);
                q.pop();
                for (ll j = 0;j < n;j ++){
                    if (!in[j] && b[u][j]){in[j]=1;q.push(j);}
                }
            }
            for (auto x:all)for (auto y:all)if (b[x][y]==0)return 0;
            for (auto x:all)in[x] = 0;
            vector <vector <ll> > comp;
            for (auto x:all){
                if (!in[x]){
                    in[x] = 1;
                    q.push(x);
                    vector <ll> tmp;
                    while (!q.empty()){
                        ll u = q.front();
                        tmp.push_back(u);
                        q.pop();
                        for (auto j:all){
                            if (!in[j] && b[u][j]==1){in[j]=1;q.push(j);}
                        }
                    }
                    for (auto y:tmp){
                        for (auto z:tmp){
                            if (b[y][z] != 1)return 0;
                        }
                    }
                    for (ll j = 0;j + 1 < sz(tmp);j ++){
                        res[tmp[j]][tmp[j+1]] = 1;
                        res[tmp[j+1]][tmp[j]] = 1;
                    }
                    comp.push_back(tmp);
                }
            }
            if (sz(comp) > 1){
                if (sz(comp)==2){
                    return 0;
                }
                else{
                    for (ll j = 0;j + 1 < sz(comp);j ++){
                        ll u = comp[j][0],v=comp[j+1][0];
                        res[u][v] = res[v][u] = 1;
                    }
                    ll u = comp[0][0],v=comp[sz(comp)-1][0];
                    res[u][v] = res[v][u] = 1;
                }
            }
        }
    }
    build(res);
    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