Submission #301172

#	Time	Username	Problem	Language	Result	Execution time	Memory
301172		rocks03	Connecting Supertrees (IOI20_supertrees)	C++14	21 / 100	248 ms	22264 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;
int p[MAXN], sz[MAXN];
void init(int n){
    iota(p, p+n, 0);
    fill(sz, sz+n, 1);
}
int find_parent(int x){
    if(x == p[x])
        return x;
    return p[x] = find_parent(p[x]);
}
bool same_set(int a, int b){
    return (find_parent(a) == find_parent(b));
}
void union_set(int a, int b){
    a = find_parent(a);
    b = find_parent(b);
    if(a == b)
        return;
    if(sz[a] < sz[b])
        swap(a, b);
    p[b] = a;
    sz[a] += sz[b];
}
int p2[MAXN], sz2[MAXN];
void init2(int n){
    iota(p2, p2+n, 0);
    fill(sz2, sz2+n, 1);
}
int find2(int x){
    if(x == p2[x])
        return x;
    return p2[x] = find2(p2[x]);
}
bool same2(int a, int b){
    return (find2(a) == find2(b));
}
void union2(int a, int b){
    a = find2(a);
    b = find2(b);
    if(a == b)
        return;
    if(sz2[a] < sz2[b])
        swap(a, b);
    p2[b] = a;
    sz2[a] += sz2[b];
}

int construct(vector<vector<int>> p){
    int N = SZ(p);
    init(N);
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(p[i][j] > 0){
                union_set(i, j);
            }
        }
    }
    vector<vector<int>> ans(N, vector<int>(N, 0));
    vector<bool> vis(N, false);
    vector<bool> vis2(N, false), vis3(N, false);
    init2(N);
    for(int i = 0; i < N; i++){
        int v = find_parent(i);
        if(!vis[v]){
            vis[v] = true;
            vector<int> vertici;
            vertici.pb(i);
            for(int j = i+1; j < N; j++){
                if(same_set(i, j)){
                    vertici.pb(j);
                }
            }

            for(int j = 0; j < SZ(vertici); j++){
                for(int k = 0; k < SZ(vertici); k++){
                    if(p[vertici[j]][vertici[k]] == 0){
                        return 0;
                    }
                }
            }
            if(SZ(vertici) == 2 && p[vertici[0]][vertici[1]] >= 2){
                return 0;
            }

            bool onlyone = true;
            for(int j = 0; j < SZ(vertici); j++){
                for(int k = 0; k < SZ(vertici); k++){
                    if(p[vertici[j]][vertici[k]] != 1){
                        onlyone = false;
                    }
                }
            }
            if(onlyone){
                for(int j = 1; j < SZ(vertici); j++){
                    ans[vertici[j-1]][vertici[j]] = 1;
                    ans[vertici[j]][vertici[j-1]] = 1;
                }
                continue;
            }

            for(int j = 0; j < SZ(vertici); j++){
                for(int k = j + 1; k < SZ(vertici); k++){
                    int v1 = vertici[j], v2 = vertici[k];
                    if(p[v1][v2] == 1){
                        union2(v1, v2);
                        vis3[find2(v1)] = true;
                    }
                }
            }
            vector<set<int>> vs;
            for(int j = 0; j < SZ(vertici); j++){
                int root = find2(vertici[j]);
                if(vis2[root] || !vis3[root]) continue;
                vis2[root] = true;
                set<int> nuovo;
                nuovo.insert(vertici[j]);
                for(int k = j+1; k < SZ(vertici); k++){
                    if(same2(vertici[j], vertici[k])){
                        nuovo.insert(vertici[k]);
                    }
                }
                vs.pb(nuovo);
            }
            set<int> c;
            for(auto x : vertici){
                int root = find2(x);
                if(!vis2[root]){
                    c.insert(x);
                }
            }

            if(!SZ(c)){
                if(SZ(vs) < 3)
                    return 0;
                for(int ind = 0; ind < SZ(vs); ind++){
                    int j = (ind - 1 + SZ(vs)) % (SZ(vs));
                    int da = *vs[j].rbegin(), a = *vs[ind].begin();
                    ans[da][a] = ans[a][da] = 1;
                    int last = -1;
                    for(auto x : vs[ind]){
                        if(last != -1){
                            ans[last][x] = ans[x][last] = 1;
                        }
                        last = x;
                    }
                }
                continue;
            }
            if(SZ(c) == 1){
                return 0;
            }
            if(SZ(c) > 1){
                for(int ind = 0; ind < SZ(vs); ind++){
                    int last = -1;
                    for(auto x : vs[ind]){
                        if(last != -1){
                            ans[last][x] = ans[x][last] = 1;
                        }
                        last = x;
                    }
                    ans[last][*c.begin()] = ans[*c.begin()][last] = 1;
                }
                int last = -1;
                for(auto x : c){
                    if(last != -1){
                        ans[last][x] = ans[x][last] = 1;
                    }
                    last = x;
                }
                ans[*c.rbegin()][*vs[0].rbegin()] = ans[*vs[0].rbegin()][*c.rbegin()] = 1;
                continue;
            }
        }
    }
    build(ans);
    return 1;
}

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