Submission #1051539

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1051539	2024-08-10T07:55:04 Z	Gromp15	Comparing Plants (IOI20_plants)	C++17	14 / 100	4000 ms	9820 KB

plants

#include <bits/stdc++.h>
#include "plants.h"
#define sz(x) (int)x.size()
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> got;

void init(int k, std::vector<int> r) {
	n = sz(r);
	adj.resize(n);
	got.resize(n);
	vector<bool> vis(n);
	for (int i = 0; i < n; i++) {
		vector<int> good;
		for (int j = 0; j < n; j++) if (!r[j] && !vis[j]) {
			bool ok = 1;
			for (int z = 1; z < k; z++) {
				int idx = j - z;
				if (idx < 0) idx += n;
				if (!vis[idx] && !r[idx]) {
					ok = 0; break;
				}
			}
			if (ok) {
				good.emplace_back(j);
			}
		}
		if (good.empty()) break;
		for (int v : good) vis[v] = 1;
		//for (int c : good) for (int j = 0; j < n; j++) if (!vis[j]) adj[c].emplace_back(j);
		for (int c : good) {
			got[c] = n - i;
			for (int j = 1; j < k; j++) {
				int idx = c - j;
				if (idx < 0) idx += n;
				r[idx]--;
			}
		}
	}
}

bool reachable(int x, int y) {
	vector<bool> vis(n);
	auto dfs = [&](auto&& s, int v) -> void {
		vis[v] = 1;
		for (int u : adj[v]) if (!vis[u]) s(s, u);
	};
	dfs(dfs, x);
	return vis[y];
}

int compare_plants(int x, int y) {
	assert(!reachable(x, y) || !reachable(y, x));
	return got[x] == got[y] ? 0 : got[x] > got[y] ? 1 : -1;
	return reachable(x, y) ? 1 : reachable(y, x) ? -1 : 0;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	0 ms	348 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #2

14.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	3 ms	528 KB	Output is correct
7	Correct	77 ms	3224 KB	Output is correct
8	Correct	1 ms	600 KB	Output is correct
9	Correct	3 ms	520 KB	Output is correct
10	Correct	76 ms	3204 KB	Output is correct
11	Correct	70 ms	3152 KB	Output is correct
12	Correct	63 ms	3412 KB	Output is correct
13	Correct	85 ms	3320 KB	Output is correct

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	3 ms	528 KB	Output is correct
7	Correct	77 ms	3224 KB	Output is correct
8	Correct	1 ms	600 KB	Output is correct
9	Correct	3 ms	520 KB	Output is correct
10	Correct	76 ms	3204 KB	Output is correct
11	Correct	70 ms	3152 KB	Output is correct
12	Correct	63 ms	3412 KB	Output is correct
13	Correct	85 ms	3320 KB	Output is correct
14	Correct	868 ms	3740 KB	Output is correct
15	Execution timed out	4070 ms	9724 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	31 ms	3116 KB	Output is correct
4	Execution timed out	4070 ms	9820 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-

Subtask #5

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Incorrect	0 ms	348 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Incorrect	0 ms	348 KB	Output isn't correct
5	Halted	0 ms	0 KB	-