Submission #305104

#	Time	Username	Problem	Language	Result	Execution time	Memory
305104		phathnv	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	256 ms	22264 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"

#define mp make_pair
#define X first
#define Y second
#define taskname " "

using namespace std;

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1000;
const int base = 7;

struct _dsu{
    int root[N], rnk[N];
    void init(int n){
        for(int i = 0; i < n; i++){
            root[i] = i;
            rnk[i] = 0;
        }
    }
    int getRoot(int u){
        if (u == root[u])
            return u;
        root[u] = getRoot(root[u]);
        return root[u];
    }
    bool unite(int u, int v){
        u = getRoot(u);
        v = getRoot(v);
        if (u == v)
            return 0;
        if (rnk[u] < rnk[v])
            swap(u, v);
        root[v] = u;
        rnk[u] += (rnk[u] == rnk[v]);
        return 1;
    }
    bool check(int u, int v){
        return (getRoot(u) == getRoot(v));
    }
} dsu;

ll hashing(const vector<int> &a){
    ll res = 0;
    for(int x : a)
        res = res * base + x;
    return res;
}

int construct(vector<vector<int>> _a){
    int n = _a.size();
    vector<vector<int>> res(n, vector<int>(n, 0));
    vector<ll> hashed(n);

    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if (_a[i][j] == 3)
                return 0;

    for(int i = 0; i < n; i++)
        hashed[i] = hashing(_a[i]);

    dsu.init(n);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if (_a[i][j] == 1 && i != j){
                if (dsu.unite(i, j)){
                    res[i][j] = res[j][i] = 1;
                }
                if (hashed[i] != hashed[j])
                    return 0;
            }

    vector <int> roots;
    for(int i = 0; i < n; i++)
        if (dsu.getRoot(i) == i){
            int cur = i;
            int cnt = 0;
            for(int j = 0; j < n; j++)
                if (_a[i][j] == 2 && dsu.getRoot(j) == j){
                    cnt++;
                    dsu.unite(i, j);
                    res[cur][j] = res[j][cur] = 1;
                    cur = j;
                }
            if (cur != i && cnt < 2)
                return 0;
            if (cur != i)
                res[i][cur] = res[cur][i] = 1;
        }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if ((_a[i][j] > 0) != dsu.check(i, j))
                return 0;

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