oj.uz

Submission #428695

# Submission time Handle Problem Language Result Execution time Memory
428695 2021-06-15T13:53:54 Z pavement Park (JOI17_park) C++17
57 / 100
 2000 ms 256012 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 Detect(int T, int N) {
	::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
0 / 10.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 88996 KB Output is correct
2 Incorrect 917 ms 256012 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 135972 KB Output is correct
2 Correct 1045 ms 177428 KB Output is correct
3 Correct 983 ms 143148 KB Output is correct
4 Correct 1316 ms 208856 KB Output is correct
5 Correct 1002 ms 141384 KB Output is correct
6 Correct 994 ms 155016 KB Output is correct
7 Correct 1047 ms 176776 KB Output is correct
8 Correct 1152 ms 177436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 582 ms 86340 KB Output is correct
2 Correct 1493 ms 226096 KB Output is correct
3 Correct 1296 ms 203688 KB Output is correct
4 Correct 887 ms 157988 KB Output is correct
5 Correct 1117 ms 196496 KB Output is correct
6 Correct 1114 ms 208216 KB Output is correct
7 Correct 802 ms 151844 KB Output is correct
8 Correct 1599 ms 244824 KB Output is correct
9 Correct 831 ms 137672 KB Output is correct
10 Correct 984 ms 151320 KB Output is correct
11 Correct 1190 ms 197080 KB Output is correct
12 Correct 1470 ms 226472 KB Output is correct
13 Correct 618 ms 111824 KB Output is correct
14 Correct 985 ms 158320 KB Output is correct
15 Correct 813 ms 128540 KB Output is correct
16 Correct 1492 ms 224456 KB Output is correct
17 Correct 417 ms 91132 KB Output is correct
18 Correct 1471 ms 240792 KB Output is correct
19 Correct 982 ms 180600 KB Output is correct
20 Correct 1387 ms 221276 KB Output is correct

Subtask #5
0 / 23.0

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