제출 #425592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
425592		Mlxa	식물 비교 (IOI20_plants)	C++14	11 / 100	56 ms	7596 KiB

plants

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#include "plants.h"


namespace my {
const int N = 303;
int n, k, kth[N], can[N];
vector<int> g[N];

struct tree_t {
	pair<int, int> arr[N];
	void build() {
		for (int i = 0; i < N; ++i) {
			arr[i].x = kth[i];
			arr[i].y = i;
		}
	}
	void range_add(int l, int r, int value) {
		for (int i = l; i < r; ++i) {
			arr[i].x += value;
		}
	}
	void cycle_add(int from, int value) {
		from %= n; from += n; from %= n;
		if (from + k <= n) {
			range_add(from, from + k, value);
		} else {
			range_add(from, n, value), range_add(0, from + k - n, value);
		}
	}
	pair<int, int> range_min(int l, int r) {
		return *min_element(arr + l, arr + r);
	}
	pair<int, int> cycle_min(int from) {
		from %= n; from += n; from %= n;
		if (from + k <= n) {
			return range_min(from, from + k);
		} else {
			return min(range_min(from, n), range_min(0, from + k - n));
		}
	}
	int single(int i) {
		assert(0 <= i && i < n);
		return arr[i].x;
	}
} tree;

void edge(int v, int u) {
	assert(0 <= v && v < n);
	assert(0 <= u && u < n);
	// cout << "edge " << v << " " << u << endl;
	g[v].push_back(u);
}

vector<int> topsort;

void extract(int v) {
	tree.range_add(v, v + 1, N);
	while (1) {
		auto e = tree.cycle_min(v - k + 1);
		if (e.x) break;
		extract(e.y);
	}
	tree.cycle_add(v - k + 1, -1);
	topsort.push_back(v);
}


void bfs(int v, bool used[N]) {
	queue<int> q;
	q.push(v);
	used[v] = true;
	while (q.size()) {
		v = q.front(); q.pop();
		for (int u : g[v]) {
			if (!used[u]) {
				q.push(u);
				used[u] = true;
			}
		}
	}
}

bool reach[N][N];
}

void init(int _k, vector<int> _r) {
	using namespace my;
	n = (int)_r.size();
	k = _k;
	copy(all(_r), kth);
	tree.build();
	while (1) {
		auto e = tree.range_min(0, n);
		if (e.x) break;
		extract(e.y);
	}
	assert((int)topsort.size() == n);
	reverse(all(topsort));
	for (int i = 0; i < n; ++i) {
		can[topsort[i]] = i;
	}
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			int d = abs(i - j);
			d = min(d, n - d);
			if (d >= k) {
				continue;
			}
			if (can[i] > can[j]) {
				edge(i, j);
			} else {
				edge(j, i);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		bfs(i, reach[i]);
	}
}

int compare_plants(int x, int y) {
	using namespace my;
	if (reach[x][y]) {
		return 1;
	} else if (reach[y][x]) {
		return -1;
	} else {
		return 0;
	}
}

#ifdef LC
#include "grader.cpp"
#endif

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25