Submission #305777

#	Time	Username	Problem	Language	Result	Execution time	Memory
305777		Dormi	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	286 ms	26232 KiB

supertrees

#include "bits/stdc++.h"
#include "supertrees.h"
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
int sz(const T &a){return int(a.size());}
const int MAXN=1e3+1;
bool gone[MAXN];
int pathnum[MAXN][MAXN];
int n;
vector<vector<int>> comps;
void dfs(int loc){
    comps.back().push_back(loc);
    gone[loc]=true;
    for(int i=0;i<n;i++){
        if(pathnum[loc][i]&&!gone[i]){
            dfs(i);
        }
    }
}
vector<vector<vector<int>>> comps2;
void dfs2(int loc){
    comps2.back().back().push_back(loc);
    gone[loc]=true;
    for(int i=0;i<n;i++){
        if(pathnum[loc][i]==1&&!gone[i]){
            dfs2(i);
        }
    }
}

int construct(vector<vector<int>> p){
    n=sz(p);
    for(int i=0;i<n;i++)for(int j=0;j<n;j++)pathnum[i][j]=p[i][j];
    for(int i=0;i<n;i++){
        if(!gone[i]){
            comps.push_back({});
            dfs(i);
        }
    }
    for(auto x:comps){
        for(int i=0;i<sz(x);i++)for(int j=i+1;j<sz(x);j++){
            if(!pathnum[x[i]][x[j]])return 0;
        }
    }
    fill(gone,gone+n,false);
    for(auto x:comps){
        comps2.push_back({});
        for(auto y:x){
            if(!gone[y]){
                comps2.back().push_back({});
                dfs2(y);
            }
        }
    }
    for(auto y:comps2){
        for(auto x:y){
            for(int i=0;i<sz(x);i++)for(int j=i+1;j<sz(x);j++){
                if(pathnum[x[i]][x[j]]!=1)return 0;
            }
        }
        for(int i=0;i<sz(y);i++){
            for(int j=i+1;j<sz(y);j++){
                for(auto x:y[i]){
                    for(auto z:y[j]){
                        if(pathnum[x][z]!=2)return 0;
                    }
                }
            }
        }
    }
    vector<vector<int>> adj(n,vector<int>(n,0));
    auto addedge=[&](int l, int r){
        adj[l][r]=1,adj[r][l]=1;
    };
    for(auto x:comps2){
        if(sz(x)==2)return 0;
        for(int i=0;i<sz(x);i++){
            if(sz(x)>1)addedge(x[i].back(),x[(i+1)%sz(x)].back());
            for(int j=1;j<sz(x[i]);j++){
                addedge(x[i][j-1],x[i][j]);
            }
        }
    }
    build(adj);
    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