Submission #304404

#	Time	Username	Problem	Language	Result	Execution time	Memory
304404		rocks03	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	267 ms	22268 KiB

supertrees

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int) (x).size())
using namespace std;

void build(vector<vector<int>> _b);

const int MAXN = 1e3+100;

class dsu{
public:
    vector<int> p, sz;
    dsu(int n){
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.resize(n, 1);
    }
    int get(int x){
        return ((x == p[x]) ? x : (p[x] = get(p[x])));
    }
    bool unite(int a, int b){
        a = get(a);
        b = get(b);
        if(a == b)
            return false;
        if(sz[a] < sz[b])
            swap(a, b);
        p[b] = a;
        sz[a] += sz[b];
        return true;
    }
    bool same(int a, int b){
        return (get(a) == get(b));
    }
};

int construct(vector<vector<int>> p){
    int N = SZ(p);
    vector<vector<int>> ans(N, vector<int>(N, 0));
    dsu a(N), b(N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(p[i][j] > 0){
                a.unite(i, j);
            }
            if(p[i][j] == 3){
                return 0;
            }
        }
    }
    vector<bool> vis(N, false), vis2(N, false);
    for(int vroot = 0; vroot < N; vroot++){
        int root = a.get(vroot);
        if(!vis[root]){
            vis[root] = true;
            vector<int> vert;
            for(int i = 0; i < N; i++){
                if(a.same(i, root)){
                    vert.pb(i);
                }
            }
            bool zero = false, one = true, due = true;
            int n = SZ(vert);
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(p[vert[i]][vert[j]] != 2)
                        due = false;
                    if(p[vert[i]][vert[j]] != 1)
                        one = false;
                    if(p[vert[i]][vert[j]] == 0)
                        zero = true;
                }
            }
            if(zero == true){
                return 0;
            }
            if(one == true){
                for(int i = 1; i < n; i++){
                    ans[vert[i-1]][vert[i]] = 1;
                    ans[vert[i]][vert[i-1]] = 1;
                }
                continue;
            }
            if(due == true){
                if(n < 3)
                    return false;
                for(int i = 1; i < n; i++){
                    ans[vert[i-1]][vert[i]] = 1;
                    ans[vert[i]][vert[i-1]] = 1;
                }
                ans[vert[0]][vert[n-1]] = 1;
                ans[vert[n-1]][vert[0]] = 1;
                continue;
            }
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(p[vert[i]][vert[j]] == 1){
                        b.unite(vert[i], vert[j]);
                    }
                }
            }
            vector<vector<int>> componenti;
            for(int i = 0; i < n; i++){
                int root = b.get(vert[i]);
                vector<int> cur;
                for(int j = 0; j < n; j++){
                    if(b.get(vert[i]) == b.get(vert[j])){
                        if(p[vert[i]][vert[j]] == 2){
                            return 0;
                        }
                        if(!vis2[root])
                            cur.pb(vert[j]);
                    }
                }
                if(!vis2[root]){
                    vis2[root] = true;
                    componenti.pb(cur);
                }
            }
            int sz = SZ(componenti);
            if(sz < 3)
                return 0;
            for(int i = 0; i < sz; i++){
                for(int j = 1; j < SZ(componenti[i]); j++){
                    ans[componenti[i][j-1]][componenti[i][j]] = 1;
                    ans[componenti[i][j]][componenti[i][j-1]] = 1;
                }
            }
            for(int i = 1; i < sz; i++){
                ans[componenti[i-1][0]][componenti[i][0]] = 1;
                ans[componenti[i][0]][componenti[i-1][0]] = 1;
            }
            ans[componenti[sz-1][0]][componenti[0][0]] = 1;
            ans[componenti[0][0]][componenti[sz-1][0]] = 1;
        }
    }
    build(ans);
    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