제출 #413594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
413594		KoD	Art Class (IOI13_artclass)	C++17	62 / 100	97 ms	11136 KiB

artclass

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

template <class T> using Vec = std::vector<T>;

struct UnionFind {
    Vec<int> par;
    int comp;
    UnionFind(const int n): par(n, -1), comp(n) {}
    int find(const int u) {
        return par[u] < 0 ? u : par[u] = find(par[u]);
    }    
    void merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return;
        }
        if (par[x] > par[y]) {
            std::swap(x, y);
        }
        par[x] += par[y];
        par[y] = x;
        comp -= 1;
    }
};

int solve(const int N, const Vec<int> R, const Vec<int> G, const Vec<int> B, const std::array<int, 4> D) {
    UnionFind dsu(N);
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < 4; ++k) {
            const auto j = i + D[k];
            if (0 <= j and j < N) {
                if (std::abs(R[i] - R[j]) <= 20 and std::abs(G[i] - G[j]) <= 20 and std::abs(B[i] - B[j]) <= 20) {
                    dsu.merge(i, j);
                }
            }
        }
    }
    if (dsu.comp <= 60) {
        return 4;
    }
    if (dsu.comp >= 30000) {
        return 3;
    }
    int white = 0;
    for (int i = 0; i < N; ++i) {
        if (R[i] >= 200 and G[i] >= 200 and B[i] >= 200) {
            white += 1;
        }
    }
    if (white <= 10) {
        return 4;
    }
    if (white >= 50000) {
        return 1;
    }
    return dsu.comp <= 3000 ? 1 : 2;
}

int style(int H, int W, int R[500][500], int G[500][500], int B[500][500]) {
    const int N = H * W;
    Vec<int> r(N), g(N), b(N);
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            r[i * W + j] = R[i][j];
            g[i * W + j] = G[i][j];
            b[i * W + j] = B[i][j];
        }
    }
    return solve(N, r, g, b, std::array<int, 4>{W, 1, -W, -1});
}

• Subtask 1: 62 / 100