Submission #404815

#	Time	Username	Problem	Language	Result	Execution time	Memory
404815		AmineTrabelsi	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	251 ms	23224 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU{
    int n;
    vector<int> parent,sz;
    DSU(int _n){
        n = _n;
        for(int i=0;i<=n;i++){
            parent.push_back(i);
            sz.push_back(1);
        }
    }
    int find(int x){
        return parent[x] = (parent[x] == x ? x : find(parent[x]));
    }
    void unite(int a,int b){
        a = find(a);
        b = find(b);
        if(a != b){
            if(sz[a] >= sz[b]){
                parent[b] = a;
                sz[a] += sz[b];
            }else{
                parent[a] = b;
                sz[b] += sz[a];
            }
        }
    }
};
int construct(vector<vector<int>> p) {
    // 21
	int n = p.size();
	vector<vector<int>> answer(n,vector<int>(n,0));
    DSU comp(n);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] >= 2)return 0;
            if(p[i][j] == 1)comp.unite(i,j);
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(p[i][j] == 0 && comp.find(i) == comp.find(j))return 0;
        }
    }
    vector<bool> vis(n,0);
    for(int i=0;i<n;i++){
        if(vis[i])continue;
        vis[i] = 1;
        for(int j=0;j<n;j++){
            if(vis[j])continue;
            if(comp.find(i) == comp.find(j)){
                answer[i][j] = answer[j][i] = 1;
                vis[j] = 1;
            }
        }
    }
	build(answer);
	return 1;
}

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 0 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4