oj.uz

답안 #428683

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428683 2021-06-15T13:50:07 Z pavement Park (JOI17_park) C++17
27 / 100
 2000 ms 257872 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(238479);

#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 2065 ms 119240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 375 ms 88480 KB Output is correct
2 Incorrect 932 ms 257872 KB Wrong Answer[5]
3 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1020 ms 135804 KB Output is correct
2 Correct 1074 ms 176256 KB Output is correct
3 Correct 889 ms 141944 KB Output is correct
4 Correct 1271 ms 213192 KB Output is correct
5 Correct 932 ms 141168 KB Output is correct
6 Correct 933 ms 155776 KB Output is correct
7 Correct 1054 ms 173636 KB Output is correct
8 Correct 1127 ms 177716 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 727 ms 117228 KB Output is correct
2 Correct 1492 ms 230784 KB Output is correct
3 Correct 1177 ms 184788 KB Output is correct
4 Correct 1257 ms 211032 KB Output is correct
5 Correct 1159 ms 191596 KB Output is correct
6 Correct 1246 ms 227460 KB Output is correct
7 Correct 623 ms 111568 KB Output is correct
8 Correct 1048 ms 171020 KB Output is correct
9 Correct 926 ms 162864 KB Output is correct
10 Correct 832 ms 143244 KB Output is correct
11 Correct 1072 ms 190488 KB Output is correct
12 Incorrect 1444 ms 252404 KB Wrong Answer[5]
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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