제출 #582075

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
582075		stevancv	Connecting Supertrees (IOI20_supertrees)	C++14	100 / 100	229 ms	24140 KiB

supertrees

#include <bits/stdc++.h>
#include "supertrees.h"
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
struct Dsu {
    vector<int> p;
    void Reset(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
    }
    int Find(int x) {
        if (x == p[x]) return x;
        return p[x] = Find(p[x]);
    }
    void Unite(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x == y) return;
        p[y] = x;
    }
};
int construct(vector<vector<int>> p) {
    int n = p.size();
    vector<vector<int>> ans(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (p[i][j] == 3) return 0;
        }
    }
    Dsu all;
    all.Reset(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (p[i][j] > 0) all.Unite(i, j);
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (all.Find(i) == all.Find(j) && p[i][j] == 0) return 0;
        }
    }
    vector<vector<int>> v(n);
    for (int i = 0; i < n; i++) {
        v[all.Find(i)].push_back(i);
    }
    vector<bool> alone(n, 1);
    for (int z = 0; z < n; z++) {
        if (v[z].size() <= 1) continue;
        vector<int> a;
        int sz = v[z].size();
        for (int i = 0; i < sz; i++) a.push_back(v[z][i]);
        Dsu d;
        d.Reset(n);
        for (int i = 0; i < sz; i++) {
            for (int j = i + 1; j < sz; j++) {
                if (p[a[i]][a[j]] == 1) {
                    d.Unite(a[i], a[j]);
                    alone[a[i]] = alone[a[j]] = 0;
                }
            }
        }
        for (int i = 0; i < sz; i++) {
            for (int j = i + 1; j < sz; j++) {
                if (d.Find(a[i]) == d.Find(a[j]) && p[a[i]][a[j]] == 2) return 0;
            }
        }
        vector<vector<int>> vv(n);
        vector<int> koji;
        for (int i = 0; i < sz; i++) {
            vv[d.Find(a[i])].push_back(a[i]);
        }
        for (int i = 0; i < sz; i++) {
            if (d.Find(a[i]) == a[i]) koji.push_back(a[i]);
        }
        int ksz = koji.size();
        if (ksz == 2) return 0;
        for (int i = 0; i < ksz; i++) {
            int x = koji[i];
            int y = koji[(i + 1) % ksz];
            if (x != y) ans[x][y] = ans[y][x] = 1;
            if (alone[x] == 1) continue;
            int sza = vv[x].size();
            for (int j = 0; j < sza - 1; j++) {
                int c1 = vv[x][j];
                int c2 = vv[x][j + 1];
                ans[c1][c2] = ans[c2][c1] = 1;
            }
        }
    }
    build(ans);
    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