Submission #1138047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138047		kh0i	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	135 ms	26212 KiB

supertrees

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

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

using ll = long long;
using pii = pair<int, int>;

#define F first
#define S second
#define sz(x) (int)((x).size())
#define all(x) (x).begin(), (x).end()

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll get_rand(ll l, ll r) {
    assert(l <= r);
    return uniform_int_distribution<ll> (l, r)(rng);
}

struct DSU{
    vector<int> p;
    DSU(int n) : p(n, -1) {}
    int find_set(int u){ return p[u] < 0 ? u : p[u] = find_set(p[u]); }

    bool join_sets(int u, int v){
        u = find_set(u), v = find_set(v);
        if(u == v)
            return 0;
        if(p[u] > p[v])
            swap(u, v);
        p[u] += p[v];
        p[v] = u;
        return 1;
    }
};

const int N = 1003;

int n, p[N][N], b[N][N];

void add_edge(int u, int v){ 
    debug(u, v);
    b[u][v] = b[v][u] = 1;
}

int construct(vector<vector<int>> p){
    n = sz(p);

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

    DSU dsu(n);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(p[i][j])
                dsu.join_sets(i, j);
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(!p[i][j] and dsu.find_set(i) == dsu.find_set(j))
                return 0;
        }
    }

    dsu = DSU(n);
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(p[i][j] == 1){
                debug(i, j);
                dsu.join_sets(i, j);
            }
        }
    }

    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            if(p[i][j] == 2 and dsu.find_set(i) == dsu.find_set(j))
                return 0;
        }
    }

    for(int i = 0; i < n; ++i){
        vector<int> comp;
        for(int j = 0; j < n; ++j){
            if(dsu.find_set(j) == i)
                comp.push_back(j);
        }
        debug(i, comp);
        for(int j = 0; j < sz(comp) - 1; ++j)
            add_edge(comp[j], comp[j + 1]);
    }

    DSU dsu2(n);
    for(int i = 0; i < n; ++i){
        if(dsu.find_set(i) != i)
            continue;
        for(int j = 0; j < n; ++j){
            if(dsu.find_set(j) != j)
                continue;
            if(p[i][j] == 2)
                dsu2.join_sets(i, j);
        }
    }

    for(int i = 0; i < n; ++i){
        vector<int> comp;
        for(int j = 0; j < n; ++j){
            if(dsu2.find_set(j) == i)
                comp.push_back(j);
        }
        if(sz(comp) < 2)
            continue;
        if(sz(comp) == 2)
        	return 0;
        debug(i, comp);
        comp.push_back(comp.front());
        for(int k = 0; k < sz(comp) - 1; ++k)
            add_edge(comp[k], comp[k + 1]);
    }

    vector<vector<int>> res;
    for(int i = 0; i < n; ++i){
    	res.push_back(vector<int>());
    	for(int j = 0; j < n; ++j)
    		res.back().push_back(b[i][j]);
    }
    build(res);
    return 1;
}

// int32_t main() {
//     cin.tie(nullptr)->sync_with_stdio(0);
//     #define task "troll"
//     if(fopen(task".inp", "r")){
//         freopen(task".inp", "r", stdin);
//         freopen(task".out", "w", stdout);
//     }
//     int test = 1;
// //    cin >> test;
//     for(int i = 1; i <= test; ++i){
// //        cout << "Case #" << i << ": ";
//         debug(solve());
//         for(int i = 0; i < n; ++i){
//             for(int j = 0; j < n; ++j){
//                 cout << b[i][j] << " \n"[j == n - 1];   
//             }
//         }
//     }
//     #ifdef LOCAL
//         cerr << "\n[Time]: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms.\n";
//     #endif
//     return 0;
// }

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