Submission #950055

#	Time	Username	Problem	Language	Result	Execution time	Memory
950055		irmuun	Connecting Supertrees (IOI20_supertrees)	C++17	100 / 100	174 ms	24292 KiB

supertrees

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

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct dsu{
    int n;
    vector<int>sz,par;
    dsu(int n):n(n){
        sz.resize(n);
        par.resize(n);
        fill(all(sz),1);
        iota(all(par),0);
    }
    int find(int x){
        if(par[x]==x) return x;
        return par[x]=find(par[x]);
    }
    void merge(int x,int y){
        x=find(x);
        y=find(y);
        if(x!=y){
            if(sz[x]<sz[y]){
                swap(x,y);
            }
            sz[x]+=sz[y];
            par[y]=x;
        }
    }
    bool same(int x,int y){
        x=find(x);
        y=find(y);
        return x==y;
    }
};

int construct(vector<vector<int>>p){
    int n=p.size();
    dsu ds(n),ds_cmp(n);
    vector<vector<int>>b(n,vector<int>(n,0));
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]>0){
                ds_cmp.merge(i,j);
            }
            if(p[i][j]==1){
                if(!ds.same(i,j)){
                    b[i][j]=1;
                    b[j][i]=1;
                    ds.merge(i,j);
                }
            }
        }
    }
    set<int>group[n];
    for(int i=0;i<n;i++){
        group[ds_cmp.find(i)].insert(ds.find(i));
    }
    vector<int>g[n];
    for(int i=0;i<n;i++){
        g[i]=vector<int>(all(group[i]));
        int sz=g[i].size();
        if(sz<2) continue;
        if(sz==2) return 0;
        for(int j=0;j<sz;j++){
            b[g[i][j]][g[i][(j+1)%sz]]=1;
            b[g[i][(j+1)%sz]][g[i][j]]=1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(p[i][j]!=1&&ds.same(i,j)) return 0;
            if(p[i][j]!=2&&p[i][j]!=0&&!ds.same(i,j)) return 0;
            if(p[i][j]==0&&ds_cmp.same(i,j)) 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