Submission #385859

#	Time	Username	Problem	Language	Result	Execution time	Memory
385859		i_am_noob	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	297 ms	24324 KiB

supertrees

#include<bits/stdc++.h>
#include "supertrees.h"
using namespace std;

#define ll long long
//#define int ll
#define rep(n) rep1(i,n)
#define rep1(i,n) rep2(i,0,n)
#define rep2(i,a,b) for(int i=a; i<(b); ++i)
#define rep3(i,a,b) for(int i=a; i>=(b); --i)
#define pb push_back
#define sz(a) ((int)a.size())
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define inf 0x3f3f3f3f3f3f3f3f
#define pow2(x) (1ll<<(x))

#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << " " << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T x){cerr << x << endl;}
template<typename T, typename ...S> void _do(T x, S... y){cerr << x << ", ";_do(y...);}
#else
#define bug(...) 49
#endif

const int maxn=1005;

struct dsu{
    int par[maxn];
    dsu(){rep(maxn) par[i]=i;}
    int Find(int x){return x==par[x]?x:par[x]=Find(par[x]);}
    void Union(int x, int y){
        x=Find(x),y=Find(y);
        if(x==y) return;
        par[x]=y;
    }
};

int construct(vector<vector<int>> p){
	int n=sz(p);
    vector<vector<int>> res;
    res.resize(n);
    rep(n) res[i].resize(n);
    dsu d1,d2;
    rep(n) rep1(j,n) if(p[i][j]) d1.Union(i,j);
    rep(n) rep1(j,n) if(!p[i][j]) if(d1.Find(i)==d1.Find(j)) return 0;
    rep(n) rep1(j,n) if(p[i][j]==3) return 0;
    vector<int> vec[maxn],vec1[maxn];
    rep(n) vec[d1.Find(i)].pb(i);
    auto make_edge=[&](int u, int v){
        res[u][v]=res[v][u]=1;
        return;
    };
    rep(n) if(sz(vec[i])>1){
        for(auto j: vec[i]) for(auto k: vec[i]) if(p[j][k]==1) d2.Union(j,k);
        for(auto j: vec[i]) for(auto k: vec[i]) if(p[j][k]!=1) if(d2.Find(j)==d2.Find(k)) return 0;
        for(auto j: vec[i]) vec1[j].clear();
        for(auto j: vec[i]) vec1[d2.Find(j)].pb(j);
        for(auto j: vec[i]) rep1(k,sz(vec1[j])-1) make_edge(vec1[j][k],vec1[j][k+1]);
        vector<int> tmp;
        for(auto j: vec[i]) if(sz(vec1[j])) tmp.pb(j);
        if(sz(tmp)==2){
            int x,y;
            if(sz(vec1[tmp[0]])>1) x=tmp[0],y=tmp[1];
            else if(sz(vec1[tmp[1]])>1) x=tmp[1],y=tmp[0];
            else return 0;
            make_edge(vec1[x][0],vec1[y][0]);
            make_edge(vec1[x][1],vec1[y][0]);
        }
        else if(sz(tmp)>=3){
            rep1(j,sz(tmp)-1) make_edge(vec1[tmp[j]][0],vec1[tmp[j+1]][0]);
            make_edge(vec1[tmp[0]][0],vec1[tmp.back()][0]);
        }
    }
    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