oj.uz

Submission #957972

# Submission time Handle Problem Language Result Execution time Memory
957972 2024-04-04T15:20:57 Z Soumya1 Park (JOI17_park) C++17
100 / 100
 264 ms 1276 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1405;
vector<int> ad[mxN], edges[mxN];
int added[mxN];
int n;
vector<int> all;
bool bad[mxN];
void get(int u) {
	all.push_back(u);
	for (int v : ad[u]) {
		if (bad[v]) continue;
		get(v);
	}
}
int find_first(vector<int> nodes, int u) {
	int ask[n];
	for (int i = 0; i < n; i++) ask[i] = 0;
	for (int i : nodes) ask[i] = 1;
	ask[u] = 1;
	if (!Ask(min(u, nodes[0]), max(nodes[0], u), ask)) return -1;
	int lo = 0, hi = nodes.size() - 1;
	while (lo < hi) {
		int mid = (lo + hi) >> 1;
		for (int i = 0; i < n; i++) ask[i] = 0;
		for (int i = 0; i <= mid; i++) ask[nodes[i]] = 1;
		ask[u] = 1;
		if (Ask(min(u, nodes[0]), max(nodes[0], u), ask)) hi = mid;
		else lo = mid + 1;
	}
	return nodes[lo];
}
void dfs(int u) {
	int ask[n];
	for (int i = 0; i < n; i++) ask[i] = added[i];
	ask[u] = 1;
	while (!Ask(0, u, ask)) {
		int lo = 0, hi = n - 1;
		while (lo < hi) {
			int mid = (lo + hi) >> 1;
			for (int i = 0; i < n; i++) {
				ask[i] = (added[i] || i <= mid);
			}
			ask[0] = ask[u] = 1;
			if (Ask(0, u, ask)) hi = mid;
			else lo = mid + 1;
		}
		dfs(lo);
		for (int i = 0; i < n; i++) ask[i] = added[i];
		ask[u] = 1;
	}
	for (int i = 0; i < n; i++) bad[i] = false;
	vector<int> roots;
	roots.push_back(0);
	int some = -1;
	for (int i = 0; i < roots.size(); i++) {
		int x = roots[i];
		while (true) {
			all.clear();
			get(x);
			int v = find_first(all, u);
			if (v == -1) break;
			some = v;
			bad[v] = true;
			edges[v].push_back(u);
			for (int childs : ad[v]) roots.push_back(childs);
			if (v == x) break;
		}
	}
	ad[some].push_back(u);
	added[u] = 1;
}
void Detect(int T, int N) {
	n = N;
	added[0] = 1;
	for (int i = 1; i < N; i++) {
		if (!added[i]) {
			dfs(i);
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j : edges[i]) {
			Answer(min(i, j), max(i, j));
		}
	}
}

Compilation message

park.cpp: In function 'void dfs(int)':
park.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for (int i = 0; i < roots.size(); i++) {
      |                  ~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 5 ms 348 KB Output is correct
3 Correct 4 ms 584 KB Output is correct
4 Correct 11 ms 564 KB Output is correct
5 Correct 19 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 824 KB Output is correct
2 Correct 96 ms 752 KB Output is correct
3 Correct 144 ms 752 KB Output is correct
4 Correct 259 ms 744 KB Output is correct
5 Correct 251 ms 836 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 908 KB Output is correct
2 Correct 127 ms 704 KB Output is correct
3 Correct 123 ms 604 KB Output is correct
4 Correct 117 ms 700 KB Output is correct
5 Correct 147 ms 976 KB Output is correct
6 Correct 123 ms 688 KB Output is correct
7 Correct 114 ms 948 KB Output is correct
8 Correct 124 ms 696 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 652 KB Output is correct
2 Correct 150 ms 716 KB Output is correct
3 Correct 160 ms 732 KB Output is correct
4 Correct 171 ms 764 KB Output is correct
5 Correct 181 ms 600 KB Output is correct
6 Correct 196 ms 812 KB Output is correct
7 Correct 189 ms 604 KB Output is correct
8 Correct 189 ms 716 KB Output is correct
9 Correct 160 ms 700 KB Output is correct
10 Correct 181 ms 756 KB Output is correct
11 Correct 191 ms 776 KB Output is correct
12 Correct 150 ms 776 KB Output is correct
13 Correct 213 ms 780 KB Output is correct
14 Correct 192 ms 740 KB Output is correct
15 Correct 214 ms 784 KB Output is correct
16 Correct 136 ms 956 KB Output is correct
17 Correct 264 ms 780 KB Output is correct
18 Correct 189 ms 600 KB Output is correct
19 Correct 230 ms 1276 KB Output is correct
20 Correct 173 ms 672 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 600 KB Output is correct
2 Correct 192 ms 956 KB Output is correct
3 Correct 154 ms 696 KB Output is correct
4 Correct 196 ms 924 KB Output is correct
5 Correct 181 ms 692 KB Output is correct
6 Correct 249 ms 856 KB Output is correct
7 Correct 220 ms 764 KB Output is correct
8 Correct 208 ms 1044 KB Output is correct
9 Correct 196 ms 604 KB Output is correct
10 Correct 156 ms 748 KB Output is correct
11 Correct 176 ms 708 KB Output is correct
12 Correct 200 ms 988 KB Output is correct
13 Correct 168 ms 720 KB Output is correct
14 Correct 189 ms 700 KB Output is correct
15 Correct 179 ms 604 KB Output is correct
16 Correct 129 ms 688 KB Output is correct
17 Correct 254 ms 836 KB Output is correct
18 Correct 173 ms 780 KB Output is correct