Submission #518520

#	Time	Username	Problem	Language	Result	Execution time	Memory
518520		tabr	Art Class (IOI13_artclass)	C++17	12 / 100	79 ms	10296 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]) {
    double rs = 0;
    double gs = 0;
    double bs = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            rs += r[i][j];
            gs += g[i][j];
            bs += b[i][j];
        }
    }
    int x = h * w;
    dsu uf(x);
    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}) < 50) {
                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}) < 50) {
                uf.unite(i * w + j, i * w + j + w);
            }
        }
    }
    rs /= x;
    gs /= x;
    bs /= x;
    int cnt = 0;
    for (int i = 0; i < x; i++) {
        if (uf.get(i) == i) {
            cnt++;
        }
    }
    if (cnt < 10) {
        return 4;
    }
    if (cnt > 100) {
        if (gs > max(rs, bs) + 30) {
            return 2;
        } else {
            return 3;
        }
    }
    assert(false);
    return -1;
}

#ifdef tabr
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    return 0;
}
#endif

• Subtask 1: 12 / 100