Submission #1073220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073220		TheQuantiX	Connecting Supertrees (IOI20_supertrees)	C++17	96 / 100	169 ms	24400 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
 
using namespace std;
using ll = long long;
 
ll n, m, q, k, x, y, a, b, c;
 
struct dsu {
    ll n;
    vector<ll> par;
    vector<ll> sz;
 
    dsu(ll N) : n(N) {
        par.resize(n);
        sz.resize(n);
        for (int i = 0; i < n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }
 
    ll find_p(ll x) {
        if (par[x] == x) {
            return x;
        }
        ll p = find_p(par[x]);
        par[x] = p;
        return p;
    }
 
    void join(ll x, ll y) {
        x = find_p(x);
        y = find_p(y);
        if (x == y) {
            return;
        }
        if (sz[y] > sz[x]) {
            swap(x, y);
        }
        par[y] = x;
        sz[x] += sz[y];
    }
};
 
int construct(vector< vector<int> > p) {
    n = p.size();
    vector< vector<int> > ans(n, vector<int>(n));
    vector< vector<ll> > comp(n);
    vector< vector<ll> > comp2(n);
    vector< vector<ll> > comp2a(n);
    dsu d(n);
    bitset<1000> bt;
    for (int i = 0; i < n; i++) {
        if (p[i][i] != 1) {
            return 0;
        }
        for (int j = 0; j < i; j++) {
            if (p[i][j] == 1) {
                d.join(i, j);
                bt.set(i);
                bt.set(j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!bt[i]) {
            continue;
        }
        comp[d.find_p(i)].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        if (!bt[i]) {
            continue;
        }
        for (int j : comp[i]) {
            for (int k : comp[i]) {
                if (p[j][k] != 1) {
                    return 0;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!bt[i]) {
            continue;
        }
        if (comp[i].size() <= 1) {
            continue;
        }
        for (int j = 0; j < comp[i].size() - 1; j++) {
            ans[comp[i][j + 1]][comp[i][j]] = 1;
            ans[comp[i][j]][comp[i][j + 1]] = 1;
        }
    }
    bitset<1000> bt2;
    bitset<1000> bt2_;
    dsu d2(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // if (bt[i] && !bt[j] && p[i][j] != 0) {
            //     return 0;
            // }
            // if (!bt[i] && bt[j] && p[i][j] != 0) {
            //     return 0;
            // }
            if (p[i][j] == 2) {
                d2.join(i, j);
                bt2_.set(i);
                bt2_.set(j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        if (!bt2_[i]) {
            continue;
        }
        ll x = i;
        if (bt[i]) {
            x = d.find_p(i);
        }
        if (bt2[x]) {
            continue;
        }
        // cout << x << endl;
        bt2.set(x);
        // cout << '\t' << d2.find_p(x) << '\n';
        comp2[d2.find_p(x)].push_back(x);
    }
    // cout << comp2[3].size() << '\n';
    for (int i = 0; i < n; i++) {
        if (comp2[i].size() <= 1) {
            continue;
        }
        if (comp2[i].size() == 2) {
            return 0;
        }
        for (int j = 0; j < comp2[i].size(); j++) {
            // cout << comp2[i][j] << '\n';
            ans[comp2[i][(j + 1) % comp2[i].size()]][comp2[i][j]] = 1;
            ans[comp2[i][j]][comp2[i][(j + 1) % comp2[i].size()]] = 1;
        }
        // cout << '\n';
    }
    dsu du(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (ans[i][j]) {
                du.join(i, j);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (du.find_p(i) == du.find_p(j) && p[i][j] == 0) {
                return 0;
            }
        }
    }
    build(ans);
    return 1;
}

Compilation message (stderr)

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

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