Submission #1271716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271716		antonn	Connecting Supertrees (IOI20_supertrees)	C++20	100 / 100	97 ms	22204 KiB

supertrees

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

#define F first
#define S second
 
using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
 
template<class T> bool ckmin(T& a, T b) { return b < a ? a = b, true : false; }
template<class T> bool ckmax(T& a, T b) { return a < b ? a = b, true : false; }

const int N = 1000 + 7;

int t[N], sz[N];

int root(int x) {
    if (t[x] == x) return x;
    return t[x] = root(t[x]); 
}

void join(int a, int b) {
    a = root(a), b = root(b);
    if (a == b) return;
    if (sz[a] < sz[b]) swap(a, b);
    t[b] = a;
    sz[a] += sz[b];
}

int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vi> sol(n, vi(n));
    for (int i = 0; i < N; ++i) t[i] = i, sz[i] = 1;
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (p[i][j] != 0) {
                join(i, j);
                if (p[i][j] == 3) return 0;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (p[i][j] == 0 && root(i) == root(j)) {
                return 0;
            }
        }
    }
    
    auto add_edge = [&](int a, int b) -> void {
        sol[a][b] = sol[b][a] = 1;
    };
    
    for (int i = 0; i < n; ++i) {
        if (root(i) != i) continue;
        vi cc;
        for (int j = 0; j < n; ++j) if (root(j) == i) cc.push_back(j);
        
        if (cc.size() == 1) {
            continue;
        }
        
        vi vis(n, 0);
        vector<int> chains;
        for (auto x : cc) {
            if (vis[x]) continue;
            vi here;
            here.push_back(x);
            vis[x] = 1;
            for (int j = 0; j < here.size(); ++j) {
                for (auto k : cc) {
                    if (!vis[k] && p[here[j]][k] == 1) {
                        here.push_back(k);
                        vis[k] = 1;
                    }
                }
            } 
            for (auto x : here) {
                for (auto y : here) {
                    if (x != y && p[x][y] == 2) return 0;
                }
            }
            for (int j = 1; j < here.size(); ++j) add_edge(here[j - 1], here[j]);
            chains.push_back(here.back());
        }
        if (chains.size() == 1) continue;
        if (chains.size() == 2) return 0;
        
        for (int j = 0; j < chains.size(); ++j) add_edge(chains[j], chains[(j + 1) % chains.size()]);
    }
    build(sol);
    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