Submission #1305949

#	Time	Username	Problem	Language	Result	Execution time	Memory
1305949		iamsazidh	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	99 ms	22192 KiB

supertrees

#include "supertrees.h"
#include <vector>
//ᴇᴀᴄʜ ᴘᴇʀꜱᴏɴ ᴡɪʟʟ ᴏɴʟʏ ʜᴀᴠᴇ ᴡʜᴀᴛ ᴛʜᴇʏ ᴇɴᴅᴇᴀᴠᴏᴜʀᴇᴅ ᴛᴏᴡᴀʀᴅꜱ [53:39]
//Author: Sazid Hasan
#include <bits/stdc++.h>
using namespace std;

typedef long long              ll;
typedef double                 dl;
typedef vector<int>            vi;
typedef vector<vector<int>>    vii;
typedef vector<ll>             vl;
typedef vector<bool>           vb;
typedef pair<int,int>         pii;
typedef pair<ll, ll>          pll;

#define ff                first
#define ss                second
#define all(a)            a.begin(),a.end()
#define gcd(a,b)          __gcd(a,b)
#define lcm(a,b)          (a*(b/gcd(a,b)))
#define spc               " "

#ifdef ONLINE_JUDGE
    #define debarr(array)
    #define deb(x)
    #define del
#else
    #define debarr(array)  for(int w = 0; w < array.size(); w++) cerr << #array << "-" << w << " = " << array[w] << endl;
    #define deb(x)         cerr << #x << " = " << x << endl;
    #define del cerr << '\n';
#endif


const double PI =         acos(-1);
const int MOD =           1000000007;
const int inf =           (2147483647);

class DSU{
private:
    vi par, sz;
public:
    DSU(int n){
        par.resize(n);
        iota(all(par), 0);
        sz.resize(n, 1);
    }
    int find(int a){
        if(par[a]==a) return a;
        return par[a] = find(par[a]);
    }
    void merge(int a, int b){
        a = find(a), b = find(b);
        if(a==b) return;
        if(sz[a]<sz[b]) swap(a, b);
        sz[a] += sz[b];
        par[b] = a;
    }
    bool same(int a, int b){
        a = find(a), b = find(b);
        return a==b;
    }



};

int construct(std::vector<std::vector<int>> p) {
    int n = p.size();
    DSU dsu(n);
    vector<vi> adj(n, vi(n, 0));
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(p[i][j]==1){
                if(!dsu.same(i, j)){
                    adj[i][j] = adj[j][i] = 1;
                    dsu.merge(i, j);
                }
            }
        }
    }
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(p[i][j]==3) return 0;
            if(p[i][j]!=1){
                if(dsu.same(i, j)) return 0;
            }
        }
    }
    vb visited(n, 0);

    for(int i = 0; i < n; i++){
        if(dsu.find(i)!=i || visited[i]) continue;
        set<int> neighboor; neighboor.insert(i);
        for(int j = i+1; j < n; j++){
            if(p[i][j]==2){ neighboor.insert(dsu.find(j)); dsu.merge(i, j); }
        }
        vi nodes(all(neighboor));
        if(nodes.size()==2)  return 0;
        if(nodes.size()==1) continue;
        for(int k = 0; k < (int)nodes.size()-1; k++) adj[nodes[k]][nodes[k+1]] = adj[nodes[k+1]][nodes[k]] = 1;
        adj[nodes[0]][nodes.back()] = adj[nodes.back()][nodes[0]] = 1;
        for(auto x: nodes) visited[x] = 1;
    }

    
    for(int i = 0; i < n; i++){
        for(int j = i+1; j < n; j++){
            if(p[i][j]==0){
                if(dsu.same(i, j)) return 0;
            }else{
                if(!dsu.same(i, j)) return 0;
            }
        }
    }


    build(adj);
    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