oj.uz

답안 #428690

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428690 2021-06-15T13:52:45 Z pavement Park (JOI17_park) C++17
27 / 100
 2000 ms 257716 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;
 
mt19937 rng(128373);
 
#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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2099 ms 124956 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 374 ms 90496 KB Output is correct
2 Incorrect 885 ms 257716 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 906 ms 137008 KB Output is correct
2 Correct 1051 ms 176012 KB Output is correct
3 Correct 956 ms 142388 KB Output is correct
4 Correct 1202 ms 212340 KB Output is correct
5 Correct 871 ms 138196 KB Output is correct
6 Correct 899 ms 154600 KB Output is correct
7 Correct 1186 ms 175040 KB Output is correct
8 Correct 1059 ms 178696 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 575 ms 98824 KB Output is correct
2 Correct 1208 ms 207624 KB Output is correct
3 Correct 1344 ms 213332 KB Output is correct
4 Correct 966 ms 155936 KB Output is correct
5 Correct 943 ms 165308 KB Output is correct
6 Correct 1092 ms 204076 KB Output is correct
7 Correct 1006 ms 190532 KB Output is correct
8 Correct 1249 ms 205948 KB Output is correct
9 Correct 1229 ms 219112 KB Output is correct
10 Correct 1135 ms 207780 KB Output is correct
11 Correct 1291 ms 235512 KB Output is correct
12 Correct 1261 ms 221096 KB Output is correct
13 Correct 722 ms 147696 KB Output is correct
14 Correct 1320 ms 232792 KB Output is correct
15 Correct 706 ms 142496 KB Output is correct
16 Correct 1092 ms 185120 KB Output is correct
17 Correct 353 ms 88540 KB Output is correct
18 Incorrect 1397 ms 251540 KB Wrong Answer[5]
19 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2071 ms 110320 KB Time limit exceeded
2 Halted 0 ms 0 KB -