제출 #1318778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1318778		AzeTurk810	Connecting Supertrees (IOI20_supertrees)	C++20	21 / 100	273 ms	26204 KiB

supertrees

/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
Music: https://www.youtube.com/watch?v=mewNjPCi76E&list=RDmewNjPCi76E&start_radio=1, https://www.youtube.com/watch?v=9ZEURntrQOg&list=RDMM&start_radio=1&rv=ePtFpGENP8s, https://www.youtube.com/watch?v=L_BPzUfFHpQ, https://www.youtube.com/watch?v=AdknTYEXXl0
*/
#include "supertrees.h"
#include <cassert>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#endif

struct DSU {
    vector<int> par;
    int n, components;

    DSU(int _n) {
        n = _n;
        components = n;
        par.assign(n, -1);
    }

    DSU() {
    }

    void init(int _n) {
        n = _n;
        components = _n;
        par.assign(_n, -1);
    }

    int Find(int u) {
        if (par[u] < 0)
            return u;
        return par[u] = Find(par[u]);
    }

    bool Union(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u != v) {
            components--;
            if (par[u] > par[v]) {
                swap(u, v);
            }
            par[u] += par[v];
            par[v] = u;
            return true;
        } else {
            return false;
        }
    }
};

vector<vector<int>> adj, _p, matrixr;
vector<char> inChain, inCycle, used; // chars
DSU t;
int _n;

void connect(const int &u, const int &v) {
    adj[v].push_back(u);
    adj[u].push_back(v);
    matrixr[u][v] = true;
    matrixr[v][u] = true;
}

void init() {
    dbg("init");
    _n = _p.size();
    assert(_p[0].size() == _n);
    inChain.assign(_n, false);
    inCycle.assign(_n, false);
    used.assign(_n, false);
    adj.resize(_n);
    matrixr.assign(_n, vector<int>(_n, false));
    t.init(_n);
    for (int i = 0; i < _n; i++) {
        for (int j = i + 1; j < _n; j++) {
            if (_p[i][j] != 0)
                t.Union(i, j);
            if (_p[i][j] == 1) {
                inChain[i] = true;
                inChain[j] = true;
            }
            if (_p[i][j] == 2) {
                inCycle[i] = true;
                inCycle[j] = true;
            }
        }
    }
    dbg("Init is over");
}

char solve() {
    for (int v = 0; v < _n; v++) {
        if (used[v])
            continue;
        // INFO: Chain is completly true
        if (inChain[v] == true && inCycle[v] == false) {
            vector<int> chain;
            chain.push_back(v);
            used[v] = true;
            for (int u = 0; u < _n; u++) {
                if (u == v)
                    continue;
                if (_p[u][v] == 1) {
                    // assert(_p[v][u] == 1);
                    used[u] = true;
                    chain.push_back(u);
                } else {
                    // assert(_p[v][u] == 0);
                }
            }
            // dbg(chain);
            for (int i = 1; i < chain.size(); i++) {
                const int &u = chain[i];
                const int &v = chain[i - 1];
                connect(u, v);
            }
            continue;
        }
        if (inCycle[v] == true) {
            vector<int> cycle;
            cycle.push_back(v);
            used[v] = true;
            for (int u = 0; u < _n; u++) {
                if (u == v)
                    continue;
                if (_p[u][v] == 2) {
                    used[u] = true;
                    cycle.push_back(u);
                }
            }
            dbg(cycle);
            for (int i = 1; i < cycle.size(); i++) {
                const int &u = cycle[i];
                const int &v = cycle[i - 1];
                connect(u, v);
            }
            // Make cycle fully
            connect(cycle.back(), cycle[0]);
            for (int i = 0; i < cycle.size(); i++) {
                const int &v = cycle[i];
                if (inChain[v] == true) {
                    vector<int> chain;
                    int lst = v;
                    for (int u = 0; u < _n; u++) {
                        if (u == v)
                            continue;
                        if (_p[u][v] == 1) {
                            used[u] = true;
                            connect(lst, u);
                            lst = u;
                        }
                    }
                }
            }
        }
    }
    return 0;
}

char check_answer() {
    dbg("Check_answer started");
    for (int u = 0; u < _n; u++) {
        for (int v = 0; v < _n; v++) {
            if (_p[u][v] != _p[v][u])
                return false; // INFO: undirected graph
        }
    }
    vector<char> vis(_n, false);
    vector<vector<int>> matrixc(_n, vector<int>(_n, false));
    int st = -1;
    function<void(int, int)> dfs = [&](int v, int pa) {
        vis[v] = true;
        for (const int &u : adj[v]) {
            if (u == pa)
                continue;
            if (matrixc[st][u] > 3 || vis[u])
                continue;
            matrixc[st][u]++;
            dfs(u, v);
        }
        vis[v] = false;
    };
    for (int i = 0; i < _n; i++) {
        st = i;
        dfs(i, -1);
    }
    dbg(_p);
    dbg(matrixc);
    for (int i = 0; i < _n; i++) {
        for (int j = 0; j < _n; j++) {
            if (i == j)
                continue;
            if (_p[i][j] != matrixc[i][j])
                return false;
        }
    }
    return true;
}

int answer() {
    dbg("answering started");
    if (!(check_answer()))
        return false;
    build(matrixr);
    return true;
}

// Attack on titan<3

int construct(std::vector<std::vector<int>> p) {
    _p = p;
    init();
    if (solve())
        return 0;
    return answer();
}

// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
*/

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