Submission #1338039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1338039		vidux	Connecting Supertrees (IOI20_supertrees)	C++17	0 / 100	1 ms	344 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;

int construct(vvi p) {
        int n = p.size();
        vvi ans(n, vi(n));
        vvi comp(n);
        vi seen(n);
        for (int c = 0; c < n; c++) {
                auto dfs = [&](auto dfs, int u) -> void {
                        if (seen[u]) return;
                        seen[u] = 1;
                        comp[c].push_back(c);
                        for (int v = 0; v < n; v++) if (p[u][v]) dfs(dfs, v);
                };
                dfs(dfs, c);
        }
        for (int c = 0; c < n; c++) if (comp.size()) {
                vvi all(4);
                vi mixed;
                for (int u : comp[c]) {
                        vi cnt(4);
                        for (int v : comp[c]) if (u != v) {
                                cnt[p[u][v]]++;
                        }
                        if (cnt[0]) return 0;
                        if (cnt[2] && cnt[3]) return 0;
                        if ((cnt[2] || cnt[3]) && cnt[1]) mixed.push_back(u);
                        else {
                                if (cnt[1]) all[1].push_back(u);
                                if (cnt[2]) all[2].push_back(u);
                                if (cnt[3]) all[3].push_back(u);
                        }
                }
                if (all[2].empty() && all[3].empty()) {
                        int prev = -1;
                        for (int u : comp[c]) {
                                if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
                                prev = u;
                        }
                }
                else if (all[3].empty()) {
                        vi twos;
                        for (int u : all[2]) {
                                if (twos.size()) ans[u][twos.back()] = ans[twos.back()][u] = 1;
                                twos.push_back(u);
                        }
                        if (twos.size() < 2) return 0;
                        if (all[1].size()) {
                                ans[twos[0]][twos.back()] = ans[twos.back()][twos[0]] = 1;
                        }
                        else {
                                int prev = -1;
                                for (int u : mixed) {
                                        if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
                                        prev = u;
                                }
                                ans[twos[0]][prev] = ans[prev][twos[0]] = 1;
                                ans[twos.back()][prev] = ans[prev][twos.back()] = 1;
                        }
                }
                else if (all[2].empty()) {
                        return 0;
                        if (all[1].size()) return 0;
                        int prev = -1;
                        for (int u : mixed) {
                                if (prev >= 0) ans[u][prev] = ans[prev][u] = 1;
                                prev = u;
                        }
                        vi threes;
                        for (int u : all[3]) {
                                if (threes.size()) ans[u][threes.back()] = ans[threes.back()][u] = 1;
                                threes.push_back(u);
                        }
                        if (threes.size() < 3) return 0;
                        ans[threes[0]][prev] = ans[prev][threes[0]] = 1;
                        ans[threes.back()][prev] = ans[prev][threes.back()] = 1;
                }
                else return 0;
        }
        build(ans);
        return 1;
}

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