oj.uz

Submission #428703

# Submission time Handle Problem Language Result Execution time Memory
428703 2021-06-15T13:57:17 Z pavement Park (JOI17_park) C++17
77 / 100
 2000 ms 244936 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(128302);

#define mp make_pair
#define mt make_tuple
#define pb push_back

static int N, Place[1405], link[1405], sz[1405];
static bool vis[1405];
vector<int> adj[1405];
map<tuple<int, int, vector<int> >, bool> ret;

bool query(int a, int b, int Place[]) {
	if (a > b) return query(b, a, Place);
	vector<int> tmp;
	for (int i = 0; i < N; i++) tmp.pb(Place[i]);
	if (ret.find(mt(a, b, tmp)) != ret.end()) return ret[mt(a, b, tmp)];
	else return ret[mt(a, b, tmp)] = Ask(a, b, Place);
}

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

vector<int> sub;

void getsub(int n) {
	for (auto u : adj[n])
		getsub(u);
	sub.push_back(n);
}

int getmid(int l, int r, vector<int> s) {
	if (s.size() == 1) return s[0];
	assert(!s.empty());
	vector<int> ret;
	for (int i = 0; i < N; i++) Place[i] = 1;
	for (int i = 0; i < s.size() / 2; i++) Place[s[i]] = 0;
	if (!query(l, r, Place)) {
		for (int i = 0; i < s.size() / 2; i++) ret.pb(s[i]);
		return getmid(l, r, ret);
	} else {
		for (int i = s.size() / 2; i < s.size(); i++) ret.pb(s[i]);
		return getmid(l, r, ret);
	}
}

void solve(int l, int r) {
	if (find(l) == find(r)) return;
	memset(Place, 0, sizeof Place);
	Place[l] = Place[r] = 1;
	if (l >= r ? query(r, l, Place) : query(l, r, Place)) {
		l >= r ? Answer(r, l) : Answer(l, r);
		adj[l].pb(r);
		vis[l] = vis[r] = 1;
		unite(l, r);
		return;
	}
	vector<int> s;
	if (vis[l]) {
		sub.clear();
		getsub(l);
		sub.pop_back();
		sort(sub.begin(), sub.end());
		for (int i = 0; i < N; i++)
			if (i != l && i != r && (!vis[i] || binary_search(sub.begin(), sub.end(), i))) s.pb(i);
	} else {
		for (int i = 0; i < N; i++)
			if (i != l && i != r) s.pb(i);
	}
	int x = getmid(l, r, s);
	solve(l, x);
	solve(x, r);
}

void solve2(int l, int r) {
	if (find(l) == find(r)) return;
	memset(Place, 0, sizeof Place);
	Place[l] = Place[r] = 1;
	if (l >= r ? query(r, l, Place) : query(l, r, Place)) {
		l >= r ? Answer(r, l) : Answer(l, r);
		unite(l, r);
		return;
	}
	int lo = 0, hi = N - 1, ans = -1;
	while (lo <= hi) {
		int mid = (lo + hi) / 2;
		memset(Place, 0, sizeof Place);
		for (int i = 0; i <= mid; i++)
			Place[i] = 1;
		Place[l] = Place[r] = 1;
		if (l >= r ? Ask(r, l, Place) : Ask(l, r, Place)) ans = mid, hi = mid - 1;
		else lo = mid + 1;
	}
	solve2(l, ans);
	solve2(ans, r);
}

void Detect(int T, int N) {
	if (T == 1) {
		for (int i = 0; i < N; i++)
			for (int j = i + 1; j < N; j++) {
				memset(Place, 0, sizeof Place);
				Place[i] = Place[j] = 1;
				if (Ask(i, j, Place)) Answer(i, j);
			}
	} else if (T == 2 || T == 3) {
		::N = N;
		for (int i = 0; i < N; i++) {
			link[i] = i;
			sz[i] = 1;
		}
		vector<int> tmp;
		int root = 0;
		for (int i = 0; i < N; i++)
			if (i != root) tmp.pb(i);
		shuffle(tmp.begin(), tmp.end(), rng);
		for (int i : tmp) solve2(root, i);
	} else {
		::N = N;
		for (int i = 0; i < N; i++) {
			link[i] = i;
			sz[i] = 1;
		}
		vector<int> tmp;
		int root = (T == 4 ? rng() % N : 0);
		for (int i = 0; i < N; i++)
			if (i != root) tmp.pb(i);
		shuffle(tmp.begin(), tmp.end(), rng);
		for (int i : tmp) solve(root, i);
	}
}

Compilation message

park.cpp: In function 'int getmid(int, int, std::vector<int>)':
park.cpp:51:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |  for (int i = 0; i < s.size() / 2; i++) Place[s[i]] = 0;
      |                  ~~^~~~~~~~~~~~~~
park.cpp:53:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for (int i = 0; i < s.size() / 2; i++) ret.pb(s[i]);
      |                   ~~^~~~~~~~~~~~~~
park.cpp:56:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for (int i = s.size() / 2; i < s.size(); i++) ret.pb(s[i]);
      |                              ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 17 ms 360 KB Output is correct
3 Correct 15 ms 332 KB Output is correct
4 Correct 15 ms 372 KB Output is correct
5 Correct 20 ms 332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 16112 KB Output is correct
2 Correct 130 ms 16068 KB Output is correct
3 Correct 120 ms 16648 KB Output is correct
4 Correct 59 ms 16080 KB Output is correct
5 Correct 67 ms 16280 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 20880 KB Output is correct
2 Correct 193 ms 20680 KB Output is correct
3 Correct 206 ms 23816 KB Output is correct
4 Correct 206 ms 23084 KB Output is correct
5 Correct 178 ms 20408 KB Output is correct
6 Correct 201 ms 23944 KB Output is correct
7 Correct 197 ms 22680 KB Output is correct
8 Correct 194 ms 21680 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 514 ms 86464 KB Output is correct
2 Correct 1290 ms 226136 KB Output is correct
3 Correct 1161 ms 203656 KB Output is correct
4 Correct 840 ms 158080 KB Output is correct
5 Correct 1040 ms 196500 KB Output is correct
6 Correct 1055 ms 208180 KB Output is correct
7 Correct 796 ms 151932 KB Output is correct
8 Correct 1338 ms 244936 KB Output is correct
9 Correct 749 ms 137832 KB Output is correct
10 Correct 780 ms 151400 KB Output is correct
11 Correct 1109 ms 197112 KB Output is correct
12 Correct 1209 ms 226540 KB Output is correct
13 Correct 538 ms 111784 KB Output is correct
14 Correct 821 ms 158380 KB Output is correct
15 Correct 635 ms 128576 KB Output is correct
16 Correct 1252 ms 224548 KB Output is correct
17 Correct 363 ms 91220 KB Output is correct
18 Correct 1202 ms 240976 KB Output is correct
19 Correct 959 ms 180644 KB Output is correct
20 Correct 1203 ms 221348 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2099 ms 107200 KB Time limit exceeded
2 Halted 0 ms 0 KB -