Submission #17163

#	Time	Username	Problem	Language	Result	Execution time	Memory
17163		erdemkiraz	Art Class (IOI13_artclass)	C++98	23 / 100	326 ms	21100 KiB

artclass

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

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

const int N = 500;

int n, m, r[N][N], g[N][N], b[N][N];
ii root[N][N];

ii f(int x, int y) {
	if(root[x][y] == ii(0, 0) or root[x][y] == ii(x, y))
		return ii(x, y);
	return root[x][y] = f(root[x][y].first, root[x][y].second);
}

void road(int x1, int y1, int x2, int y2, int k) {
	bool flag = 0;
	if(x2 < n and y2 < m) {
		flag = 1;
		flag &= abs(r[x1][y1] - r[x2][y2]) <= k;
		flag &= abs(g[x1][y1] - g[x2][y2]) <= k;
		flag &= abs(b[x1][y1] - b[x2][y2]) <= k;
	}
	if(flag) {
		int X1 = f(x1, y1).first;
		int Y1 = f(x1, y1).second;
		int X2 = f(x2, y2).first;
		int Y2 = f(x2, y2).second;
		root[X1][Y1] = ii(X2, Y2);
	}
}

bool h[N][N];

int style(int n, int m, int R[500][500], int G[500][500], int B[500][500]) {
	:: n = n;
	:: m = m;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			r[i][j] = R[i][j];
			g[i][j] = G[i][j];
			b[i][j] = B[i][j];
		}
	}
	//printf("n = %d m = %d\n", n, m);
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			road(i, j, i, j + 1, 20);
			road(i, j, i + 1, j, 20);
		}
	}
	set < ii > cntr;
	multiset < ii > cntrMul;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			cntr.insert(f(i, j));
			cntrMul.insert(f(i, j));
		}
	}
	if(cntr.size() <= 100)
		return 4;
	int bigs = 0;
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < m; j++) {
			int x = f(i, j).first;
			int y = f(i, j).second;
			if(!h[x][y]) {
				h[x][y] = 1;
				if(cntrMul.count(ii(x, y)) >= 1000) {
					bigs++;
				}
			}
		}
	}
	//printf("bigs = %d\n", bigs);
	//printf("cntr = %d\n", (int) cntr.size());
	if(bigs >= 15)
		return 1;
	return 3;
}

• Subtask 1: 23 / 100