Submission #1132107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132107		StefanSebez	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	143 ms	26112 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1050;
vector<int>E[N];
bool was[N];vector<int>temp;
void DFS(int u){
    was[u]=true;
    temp.pb(u);
    for(auto i:E[u]) if(!was[i]) DFS(i);
}
vector<pair<int,int>>edges;
vector<vector<int>>res;
int construct(std::vector<std::vector<int>> p){
    int n=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]!=p[j][i]||p[i][j]==3) return 0;
            if(i!=j&&p[i][j]!=0) E[i].pb(j);
        }
    }
    vector<vector<int>>komp;
    for(int i=0;i<n;i++){
        if(!was[i]){
            temp.clear();
            DFS(i);
            komp.pb(temp);
            temp.clear();
        }
    }
    for(int i=0;i<n;i++) E[i].clear(),was[i]=false;
    for(auto ind:komp){
        //for(auto i:ind) printf("%i ",i);printf("\n");
        for(auto i:ind){
            for(auto j:ind){
                if(p[i][j]==1&&i!=j) E[i].pb(j);
                if(p[i][j]==0) return 0;
            }
        }
        vector<vector<int>>stabla;
        for(auto i:ind){
            if(!was[i]){
                temp.clear();
                DFS(i);
                stabla.pb(temp);
                temp.clear();
            }
        }
        for(auto idx:stabla){
            for(auto i:idx){
                for(auto j:idx){
                    if(p[i][j]!=1) return 0;
                }
            }
        }
        //printf("%i\n",stabla.size());
        //for(auto idx:stabla){for(auto i:idx) printf("%i ",i);printf("\n");}
        for(auto idx:stabla){
            for(int i=1;i<idx.size();i++) edges.pb({idx[i-1],idx[i]});
        }
        vector<int>ciklus;for(auto idx:stabla) ciklus.pb(idx[0]);
        if(ciklus.size()>1){
            for(int i=1;i<ciklus.size();i++) edges.pb({ciklus[i-1],ciklus[i]});
            edges.pb({ciklus.back(),ciklus[0]});
        }
        if(ciklus.size()==2) return 0;
        for(auto idx:stabla){
            for(auto i:idx){
                for(auto idx1:stabla){
                    if(idx==idx1) continue;
                    for(auto j:idx1){
                        if(p[i][j]!=2) return 0;
                    }
                }
            }
        }
        for(auto i:ind) E[i].clear(),was[i]=false;
    }
    res.resize(n);for(int i=0;i<n;i++) res[i].resize(n);
    for(int i=0;i<n;i++) for(int j=0;j<n;j++) res[i][j]=0;
    //for(auto [u,v]:edges) printf("{%i %i} ",u,v);printf("\n");
    for(auto [u,v]:edges) 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