Submission #433654

#	Time	Username	Problem	Language	Result	Execution time	Memory
433654		magmag	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	300 ms	26076 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
 
struct UF {
    vi p, rnk;
    int nsets;
 
    UF(int n) {
        p = vi(n);
        for (int i = 0; i < n; ++i)p[i] = i;
        rnk = vi(n);
        nsets = n;
    }
 
    int parent(int i) {
        if (p[i] == i)return i;
        return p[i] = parent(p[i]);
    }
     
    bool check(int a, int b) {
        return parent(a) == parent(b);
    }
     
    void join(int a, int b) {
        if (check(a,b))return;
        nsets--;
     
        a = parent(a);
        b = parent(b);
     
        if (rnk[a] > rnk[b]) {
            p[b] = a;
        } else {
            p[b] = a;
            if (rnk[a] == rnk[b]) {
                rnk[b]++;
            }
        }
    }
};
 
int construct2(vector<vi> p) {
    int n = p.size();
 
    UF uf(n);
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)continue;
            if (p[i][j] == 2) {
                uf.join(i,j);
            } else {
                if (uf.check(i,j))return 0;
            }
        }
    }
 
    vector<vi> ring(n);
 
    for (int i = 0; i < n; ++i) {
        ring[uf.parent(i)].push_back(i);
    }
 
    vector<vi> ans(n, vi(n, 0));
 
    for (auto vv : ring) {
        if (vv.size() <= 1)continue;
        if (vv.size() == 2)return 0;
 
        for (int i = 0; i < vv.size(); ++i) {
            int pp = (i == 0 ? vv.back() : vv[i-1]);
            ans[vv[i]][pp] = 1;
            ans[pp][vv[i]] = 1;
        }
    }
    build(ans);
    return 1;
}
 
int construct(vector<vi> p) {
    int n = p.size();
 
    for (auto vv : p) {
        for (auto x : vv) {
            if (x == 2)return construct2(p);
        }
    }
 
    UF uf(n);
 
    vector<vi> ans(n, vi(n, 0));
 
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (i == j)continue;
            if (p[i][j]) {
                uf.join(i,j);
            } else {
                if (uf.check(i,j))return 0;
            }
        }
    }
 
    for (int i = 0; i < n; ++i) {
        int par = uf.parent(i);
        if (par == i)continue;
        ans[i][par] = 1;
        ans[par][i] = 1;
    }
 
    build(ans);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct2(std::vector<std::vector<int> >)':
supertrees.cpp:72:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |         for (int i = 0; i < vv.size(); ++i) {
      |                         ~~^~~~~~~~~~~

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