답안 #1051539

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1051539	2024-08-10T07:55:04 Z	Gromp15	식물 비교 (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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-