Submission #572732

#	Time	Username	Problem	Language	Result	Execution time	Memory
572732		kartel	Connecting Supertrees (IOI20_supertrees)	C++14	96 / 100	222 ms	24176 KiB

supertrees

#include <bits/stdc++.h>
//#include "grader.cpp"
#include "supertrees.h"
#define sz(x) (int)x.size()
#define pb push_back
using namespace std;

const int N = 1e3 + 500;

int pr[N];
int prl[N];

int f(int v) {return (pr[v] == v ? v : pr[v] = f(pr[v]));}
void link(int a, int b) {
    a = f(a); b = f(b);
    if (a == b) {
        return;
    }
    pr[a] = b;
}

int fl(int v) {return (prl[v] == v ? v : prl[v] = fl(prl[v]));}
void linkl(int a, int b) {
    a = fl(a); b = fl(b);
    if (a == b) {
        return;
    }
    prl[a] = b;
}

int construct(vector <vector <int> > p) {
    int n = sz(p);
    for (int i = 0; i < n; i++) {
        pr[i] = i;
        prl[i] = i;
    }
    vector <int> cnt(4, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 1 && i != j) {
                link(i, j);
            }
            cnt[p[i][j]]++;
            if (p[i][j] > 0 && i != j) {
                linkl(i, j);
            }
        }
    }
    if (cnt[2] && cnt[3]) {
        return 0;
    }

    vector <vector <int> > b(n, vector <int> (n, 0));
    vector <set<int> > cp(n);
    set<int> cpp;

    for (int i = 0; i < n; i++) {
        cp[fl(i)].insert(i);
        cpp.insert(fl(i));
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (fl(i) == fl(j) && !p[i][j]) {
                return 0;
            }
        }
    }

    vector <int> used(n, 0);
    for (auto pp : cpp) {
        set <int> cyc;
        vector <int> c;
        for (auto i : cp[pp]) {
            if (cyc.count(f(i))) {
                continue;
            }
            cyc.insert(f(i));
            c.pb(i);
        }

        if (cnt[3] && (sz(cyc) == 3 || sz(cyc) == 2)) {
            return 0;
        }
        if (cnt[2] && sz(cyc) == 2) {
            return 0;
        }

        for (int i = 0; i < sz(c); i++) {
            b[c[i]][c[(i + 1) % sz(c)]] = 1;
            b[c[(i + 1) % sz(c)]][c[i]] = 1;
        }

        if (cnt[3]) {
            b[c[1]][c[2]] = 1;
            b[c[2]][c[1]] = 1;
        }

        vector <vector <int> > cmp(n);
        set <int> cmps;
        for (auto i : cp[pp]) {
            cmp[f(i)].pb(i);
            cmps.insert(f(i));
        }

        int it = 0;
        for (auto i : cp[pp]) {
            if (sz(cmp[i])) {
                int last = cmp[i][0];
                for (auto x : cmp[i]) {
                    if (x == last) {
                        continue;
                    }
                    b[last][x] = 1;
                    b[x][last] = 1;
                    last = x;
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        b[i][i] = 0;
    }

    build(b);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:106:13: warning: unused variable 'it' [-Wunused-variable]
  106 |         int it = 0;
      |             ^~

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