Submission #720628

#	Time	Username	Problem	Language	Result	Execution time	Memory
720628		Toxtaq	Connecting Supertrees (IOI20_supertrees)	C++17	21 / 100	182 ms	22088 KiB

supertrees

#ifndef SUPERTREES_H_INCLUDED
#define SUPERTREES_H_INCLUDED
#include "supertrees.h"
#include<bits/stdc++.h>
using namespace std;
struct DSU{
    vector<int>par;
    DSU(int n){
        par.assign(n, -1);
    }
    int FindRep(int u){
        if(par[u] < 0)return u;
        return par[u] = FindRep(par[u]);
    }
    void Union(int u, int v){
        u = FindRep(u);
        v = FindRep(v);
        if(u == v)return;
        if(par[u] > par[v])swap(u, v);
        par[u] += par[v];
        par[v] = u;
    }
    bool IsConnected(int u, int v){
        u = FindRep(u);
        v = FindRep(v);
        return (u == v);
    }
};
void build(vector<vector<int>>b);
int construct(vector<vector<int>>p){
    int n = p.size();
    DSU dsu1(n);
    vector<vector<int>>b(n, vector<int>(n));
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            if(p[i][j] && i != j){
                if(dsu1.IsConnected(i, j))continue;
                dsu1.Union(i, j);
                b[i][j] = b[j][i] = 1;
            }
        }
    }
    for(int i = 0;i < n;++i){
        for(int j = 0;j < n;++j){
            if(i != j && !p[i][j] && dsu1.IsConnected(i, j))return 0;
        }
    }
    build(b);
    return 1;
}


#endif // SUPERTREES_H_INCLUDED

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