Submission #1190458

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190458		anmattroi	Connecting Supertrees (IOI20_supertrees)	C++17	40 / 100	116 ms	22244 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;

int par[maxn], n, slt;
int find_set(int v) {
    return par[v] < 0 ? v : par[v] = find_set(par[v]);
}

void union_set(int u, int v) {
    u = find_set(u);
    v = find_set(v);
    if (u == v) return;
    if (par[u] < par[v]) swap(u, v);
    --slt;
    par[v] += par[u];
    par[u] = v;
}

map<int, vector<int> > nho;
vector<vector<int> > a;

int solve(vector<int> cur, vector<vector<int> > &ans, const vector<vector<int> > &p) {
    int mx = 0, mn = INT_MAX;
    for (int i = 0; i < cur.size(); i++)
    for (int j = i+1; j < cur.size(); j++) {
        mn = min(mn, p[cur[i]][cur[j]]);
        mx = max(mx, p[cur[i]][cur[j]]);
    }
    if (mx >= cur.size()) return 0;
    if (mx == 0) return 1;
    if (mx == 1) {
        for (int i = 1; i < cur.size(); i++)
            ans[cur[i]][cur[i-1]] = ans[cur[i-1]][cur[i]] = 1;
        return 1;
    }
    if (mx == 2 && mn == 2) {
        for (int i = 1; i < cur.size(); i++)
            ans[cur[i]][cur[i-1]] = ans[cur[i-1]][cur[i]] = 1;
        ans[cur[0]][cur.back()] = ans[cur.back()][cur[0]] = 1;
        return 1;
    }
    for (int i : cur) par[i] = -1;
    slt = cur.size();
    for (int i = 0; i < cur.size(); i++) for (int j = i+1; j < cur.size(); j++)
        if (p[cur[i]][cur[j]] == 1) union_set(cur[i], cur[j]);
    for (int i = 0; i < cur.size(); i++) for (int j = i+1; j < cur.size(); j++)
        if (p[cur[i]][cur[j]] != 1 && find_set(cur[i]) == find_set(cur[j])) return 0;

    vector<int> A;
    if (1) {
        set<int> s;
        for (int i : cur) if (-par[find_set(i)] > 1) s.insert(find_set(i));
        A = vector<int>(s.begin(), s.end());
    }
    if (A.size() == 0) return 0;
    if (A.size() == 1) {
        vector<int> C, D;
        int condition = 1;
        for (int i : cur) if (find_set(i) == A[0]) C.emplace_back(i);
        else D.emplace_back(i);
        for (int i = 0; i < C.size(); i++) for (int j = i+1; j < C.size(); j++) if (p[C[i]][C[j]] != 1) condition = 0;
        for (int i = 0; i < D.size(); i++) for (int j = i+1; j < D.size(); j++) if (p[D[i]][D[j]] != 2) condition = 0;
        for (int i = 0; i < C.size(); i++) for (int j = 0; j < D.size(); j++) if (p[C[i]][D[j]] != 2) condition = 0;
        if (D.size() < 2 || !condition) return 0;
        for (int i = 1; i < C.size(); i++) ans[C[i]][C[i-1]] = ans[C[i-1]][C[i]] = 1;
        ans[C.back()][D[0]] = ans[D[0]][C.back()] = 1;
        for (int i = 1; i < D.size(); i++) ans[D[i-1]][D[i]] = ans[D[i]][D[i-1]] = 1;
        ans[D.back()][C.back()] = ans[C.back()][D.back()] = 1;
        return 1;
    }
    if (A.size() != 2) return 0;
    vector<int> C, D, E;
    int condition = 1;
    for (int i : cur)
        if (find_set(i) == A[0]) C.emplace_back(i);
        else if (find_set(i) == A[1]) E.emplace_back(i);
        else D.emplace_back(i);
    for (int i = 0; i < C.size(); i++) for (int j = i + 1; j < C.size(); j++) if (p[C[i]][C[j]] != 1) condition = 0;
    for (int i = 0; i < E.size(); i++) for (int j = i + 1; j < E.size(); j++) if (p[E[i]][E[j]] != 1) condition = 0;
    for (int i = 0; i < D.size(); i++) for (int j = i + 1; j < D.size(); j++) if (p[D[i]][D[j]] != 2) condition = 0;
    for (int i = 0; i < C.size(); i++) for (int j = 0; j < E.size(); j++) if (p[C[i]][E[j]] != 2) condition = 0;
    for (int i = 0; i < C.size(); i++) for (int j = 0; j < D.size(); j++) if (p[C[i]][D[j]] != 2) condition = 0;
    for (int i = 0; i < E.size(); i++) for (int j = 0; j < D.size(); j++) if (p[E[i]][D[j]] != 2) condition = 0;
    if (D.empty() || !condition) return 0;
    for (int i = 1; i < C.size(); i++) ans[C[i-1]][C[i]] = ans[C[i]][C[i-1]] = 1;
    for (int i = 1; i < E.size(); i++) ans[E[i-1]][E[i]] = ans[E[i]][E[i-1]] = 1;
    for (int i = 1; i < D.size(); i++) ans[D[i-1]][D[i]] = ans[D[i]][D[i-1]] = 1;
    ans[C.back()][E[0]] = ans[E[0]][C.back()] = 1;
    ans[C.back()][D[0]] = ans[D[0]][C.back()] = 1;
    ans[D.back()][E[0]] = ans[E[0]][D.back()] = 1;
    return 1;
}

int construct(vector<vector<int>> p) {
    n = p.size();
    fill(par, par+n, -1);

    for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
    if (p[i][j]) union_set(i, j);

    for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
    if (!p[i][j] && find_set(i) == find_set(j)) return 0;

    for (int i = 0; i < n; i++) nho[find_set(i)].emplace_back(i);

    for (auto [x, vi] : nho) a.push_back(vi);

    vector<vector<int> > ans(n, vector<int>(n, 0));

    for (auto &vi : a)
        if (!solve(vi, ans, p)) return 0;

    build(ans);
    return 1;
}

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