Submission #800270

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
800270	2023-08-01T12:56:02 Z	LittleCube	Comparing Plants (IOI20_plants)	C++17	11 / 100	583 ms	5532 KB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
using namespace std;

int n, state[300];
vector<int> E[300];

void init(int k, vector<int> r)
{
	n = r.size();
	for (int i = 0; i < n; i++)
	{
		r[i] = k - 1 - r[i];
		if (r[i] == 0)
		{
			state[i] = 1;
			for (int t = 1; t < k; t++)
				E[i].emplace_back((i + t) % n);
		}
	}
	for (int it = 0; it < n; it++)
	{
		int cur = -1;
		for (int j = 0; j < n; j++)
			if (state[j] == 1)
			{
				int cnt = 0;
				for (int t = 1; t < k; t++)
					cnt += state[(j - t + n) % n] == 1;
				if (cnt == 0)
				{
					cur = j;
					break;
				}
			}
		state[cur] = 2;
		for (int t = 1; t < k; t++)
			if (--r[(cur - t + n) % n] == 0)
			{
				E[cur].emplace_back((cur - t + n) % n);
				state[(cur - t + n) % n] = 1;
			}

		for (int t = 1; t < k; t++)
			if (state[(cur + t) % n] <= 1)
				E[cur].emplace_back((cur + t) % n);
	}
	return;
}

bool reach(int x, int y)
{
	vector<int> vis(n, 0);
	queue<int> q;
	q.emplace(x);
	vis[x] = 1;
	while (!q.empty())
	{
		int u = q.front();
		if (u == y)
			return true;
		q.pop();
		for (auto v : E[u])
			if (!vis[v])
			{
				vis[v] = 1;
				q.emplace(v);
			}
	}
	return false;
}

int compare_plants(int x, int y)
{
	if (reach(x, y))
		return -1;
	if (reach(y, x))
		return 1;
	return 0;
}

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	58 ms	3056 KB	Output is correct
7	Runtime error	28 ms	5532 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	2 ms	212 KB	Output is correct
6	Runtime error	5 ms	980 KB	Execution killed with signal 11
7	Halted	0 ms	0 KB	-

Subtask #3

0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	2 ms	212 KB	Output is correct
6	Runtime error	5 ms	980 KB	Execution killed with signal 11
7	Halted	0 ms	0 KB	-

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Runtime error	37 ms	5216 KB	Execution killed with signal 11
4	Halted	0 ms	0 KB	-

Subtask #5

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct
6	Correct	3 ms	340 KB	Output is correct
7	Correct	61 ms	1140 KB	Output is correct
8	Correct	325 ms	1236 KB	Output is correct
9	Correct	87 ms	1228 KB	Output is correct
10	Correct	321 ms	1220 KB	Output is correct
11	Correct	68 ms	1148 KB	Output is correct
12	Correct	107 ms	1144 KB	Output is correct
13	Correct	583 ms	1388 KB	Output is correct

Subtask #6

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Runtime error	1 ms	340 KB	Execution killed with signal 11
6	Halted	0 ms	0 KB	-

Subtask #7

0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	58 ms	3056 KB	Output is correct
7	Runtime error	28 ms	5532 KB	Execution killed with signal 11
8	Halted	0 ms	0 KB	-