Submission #518548

#	Time	Username	Problem	Language	Result	Execution time	Memory
518548		tabr	Art Class (IOI13_artclass)	C++17	98 / 100	69 ms	5212 KiB

artclass

#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

#ifndef tabr
#include "artclass.h"
#endif

struct dsu {
    vector<int> p;
    vector<int> sz;
    int n;

    dsu(int _n) : n(_n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }

    inline int get(int x) {
        if (p[x] == x) {
            return x;
        } else {
            return p[x] = get(p[x]);
        }
    }

    inline bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) {
            return false;
        }
        if (sz[x] > sz[y]) {
            swap(x, y);
        }
        p[x] = y;
        sz[y] += sz[x];
        return true;
    }

    inline bool same(int x, int y) {
        return (get(x) == get(y));
    }
};

int style(int h, int w, int r[500][500], int g[500][500], int b[500][500]) {
    dsu uf(h * w);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) {
            int dr = abs(r[i][j] - r[i][j + 1]);
            int dg = abs(g[i][j] - g[i][j + 1]);
            int db = abs(b[i][j] - b[i][j + 1]);
            if (min({dr, dg, db}) < 20) {
                uf.unite(i * w + j, i * w + j + 1);
            }
        }
    }
    for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w; j++) {
            int dr = abs(r[i][j] - r[i + 1][j]);
            int dg = abs(g[i][j] - g[i + 1][j]);
            int db = abs(b[i][j] - b[i + 1][j]);
            if (min({dr, dg, db}) < 20) {
                uf.unite(i * w + j, i * w + j + w);
            }
        }
    }
    int cnt = 0;
    for (int i = 0; i < h * w; i++) {
        if (uf.get(i) == i) {
            cnt++;
        }
    }
    double ratio1 = 1.0 * cnt / (h * w);
    cnt = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            int dr = abs(r[i][j] - 120);
            int dg = abs(g[i][j] - 100);
            int db = abs(b[i][j] - 50);
            if (max({dr, dg, db}) < 30) {
                cnt++;
            }
        }
    }
    double ratio2 = 1.0 * cnt / (h * w);
    debug(ratio1);
    debug(ratio2);
    if (ratio1 < 0.00005) {
        return 4;
    }
    if (ratio1 > 0.05) {
        return 3;
    }
    if (ratio2 > 0.02) {
        return 2;
    }
    return 1;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int h, w;
    cin >> h >> w;
    int r[500][500];
    int g[500][500];
    int b[500][500];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> r[i][j] >> g[i][j] >> b[i][j];
        }
    }
    cout << style(h, w, r, g, b) << '\n';
    return 0;
}
#endif

• Subtask 1: 98 / 100