Submission #1291667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291667		lambd47	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	103 ms	30304 KiB

supertrees

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

using namespace std;
#define ll long long
#define L(i,j,k) for(int i=(j);i<=(k);i++)
#define R(i,j,k) for(int i=(j);i>=(k);i--)
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
    vector<vector<pair<int,int>>> adj(n);
    vector<vector<int>> answer(n,vector<int> (n,0));
    vector<int> cnt1(n,1);
    L(i,0,n-1){
        if(p[i][i]!=1)return 0;
        L(j,0,n-1){
            if(p[i][j]==3)return 0;
            if(i!=j && p[i][j]!=0){
                adj[i].push_back({j,p[i][j]});
                if(p[i][j]==1)cnt1[i]++;
            }
        }
    }
    vector<vector<int>> grupos;
    int gat=0;
    vector<int> grupo(n,-1);

    auto dfsg=[&](auto&& self, int node,int g)->void{
        grupos.back().push_back(node);
        grupo[node]=g;
        for(auto [a,t]:adj[node]){
            if(grupo[a]==-1){
                self(self,a,g);
            }
        }
        return;
    };
    L(i,0,n-1){
        if(grupo[i]==-1){
            grupos.push_back({});
            dfsg(dfsg,i,gat);
            gat++;
        }
    }
    for(auto& g:grupos){//grupos sao conexos
        for(auto&a :g){
            for(auto&b:g){
                if(p[a][b]==0)return 0;
            }
        }
    }
    vector<int> goat(n,-1);
    vector<vector<int>> sub(n);


    for(auto&g: grupos){
        int cnt=0;
        vector<int> goats;
        for(auto a:g){
            if(goat[a]==-1){
                goats.push_back(a);
                cnt++;
                goat[a]=a;
                sub[a].push_back(a);
                for(auto [b,tipo]:adj[a]){
                    if(tipo!=1)continue;
                    answer[a][b]=answer[b][a]=1;
                    goat[b]=a;
                    sub[a].push_back(b);
                }
            }
        }
        for(auto a:g){
            if(sub[a].empty())continue;
            for(auto b:sub[a]){
                for(auto c:sub[a]){
                    if(p[b][c]!=1)return 0;
                }
                if(cnt1[b]!=sz(sub[a]))return 0;//garanto que o resto estrito eh com 2
            }
        }
        if(cnt==2)return 0;
        if(cnt==1)continue;
        L(i,0,sz(goats)-1){
            int xx=goats[i%sz(goats)];
            int yy=goats[(i+1)%sz(goats)];
            answer[xx][yy]=answer[yy][xx]=1;
        }
    }
	build(answer);
	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