Submission #1178844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178844		guagua0407	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	121 ms	22272 KiB

supertrees

#include "supertrees.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    struct DSU{
        vector<int> e;
        DSU(int n){
            e=vector<int>(n,-1);
        }
        int find(int x){
            return (e[x]<0?x:e[x]=find(e[x]));
        }
        bool same(int a,int b){
            return find(a)==find(b);
        }
        bool unite(int a,int b){
            a=find(a);
            b=find(b);
            if(a==b) return false;
            if(e[a]>e[b]) swap(a,b);
            e[a]+=e[b];
            e[b]=a;
            return true;
        }
    };
}

int construct(std::vector<std::vector<int>> p) {
	int n = p.size();
	DSU dsu(n);
	DSU dsu1(n);
	for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]>0) dsu.unite(i,j);
            if(p[i][j]==1) dsu1.unite(i,j);
            if(p[i][j]==3) return 0;
        }
	}
	for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if((p[i][j]==0 and dsu.same(i,j)) or (p[i][j]>0 and !dsu.same(i,j))){
                return 0;
            }
        }
	}
    vector<vector<int>> a(n),a1(n);
    for(int i=0;i<n;i++){
        a[dsu.find(i)].push_back(i);
        a1[dsu1.find(i)].push_back(i);
    }
    vector<vector<int>> b(n,vector<int>(n));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            b[i][j]=0;
        }
    }
    bool tf=true;
    auto add=[&](int x,int y){
        b[x][y]=1;
        b[y][x]=1;
    };
    auto path=[&](vector<int> vec){
        for(int i=0;i<(int)vec.size()-1;i++){
            add(vec[i],vec[i+1]);
        }
    };
    auto cycle=[&](vector<int> vec){
        if((int)vec.size()==1) return;
        if((int)vec.size()==2){
            tf=false;
            return;
        }
        for(int i=0;i<(int)vec.size();i++){
            add(vec[i],vec[(i+1)%(int)vec.size()]);
        }
    };
    for(int i=0;i<n;i++){
        if((int)a[i].size()<=1) continue;
        if(p[a[i][0]][a[i][1]]==2 and (int)a[i].size()==2) return 0;
        vector<vector<int>> tmp;
        for(auto v:a[i]){
            if(!a1[v].empty()) tmp.push_back(a1[v]);
        }
        vector<int> cyc;
        for(auto v:tmp){
            path(v);
            cyc.push_back(v[0]);
        }
        cycle(cyc);
    }
    if(!tf) return 0;
    build(b);
	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