oj.uz

Submission #550331

# Submission time Handle Problem Language Result Execution time Memory
550331 2022-04-17T21:25:42 Z LucaDantas Park (JOI17_park) C++17
10 / 100
 80 ms 824 KB 
// I haven't checked it in a tree because the sample doesn't have a tree example so I'll test if later if I get wa (which I'll probably get)
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(random_device{}());

int rnd(int x) { return (rng() % x + x) % x; }

constexpr int maxn = 1410;

static int Place[1400];

int ask[maxn];

int Ask2(int a, int b, int c[]) { if(a > b) swap(a, b); return Ask(a, b, c); }
void Answer2(int a, int b) { if(a > b) swap(a, b); Answer(a, b); }

int edge(int a, int b) {
	// ask if there is a direct edge between a and b
	memset(ask, 0, sizeof ask);
	ask[a] = ask[b] = 1;
	return Ask2(a, b, ask);
}

array<vector<int>, 2> group(int a, int b, vector<int> tot) {
	// we know there is an edge between a and b
	
	array<vector<int>, 2> ans = {vector<int>(1, a), vector<int>(1, b)};

	int n = (int)(tot.size());
	for(int i = 0; i < n; i++) {
		if(tot[i] == a || tot[i] == b) continue;

		memset(ask, 0, sizeof ask);
		for(int j = 0; j < n; j++)
			if(tot[j] != b) ask[tot[j]] = 1;
		ask[a] = 1, ask[b] = 0; // just to make sure

		ans[Ask2(a, tot[i], ask)].push_back(tot[i]);
	}

	return ans; // we return the elements that belong to A's subtree and those that belong to B's subtree
}

int find_edge(int a, vector<int> possible) {
	shuffle(possible.begin(), possible.end(), rng);
	for(int b : possible)
		if(b != a && edge(a, b)) return b;
	assert(0);
	return -1;
}

void go(vector<int> possible) {
	if(possible.size() <= 1) return;
	if(possible.size() == 2) {
		Answer2(possible[0], possible[1]);
		return;
	}
	int a = possible[rnd(possible.size())];
	int b = find_edge(a, possible);
	Answer2(a, b);

	array<vector<int>, 2> grp = group(a, b, possible);

	go(grp[0]);
	go(grp[1]);
}

void Detect(int T, int N) {
	if(T == 1) {
		for(int i = 0; i < N; i++)
			for(int j = i+1; j < N; j++)
				if(edge(i, j)) Answer2(i, j);
		return;
	}
	vector<int> all(N);
	iota(all.begin(), all.end(), 0);
	shuffle(all.begin(), all.end(), rng);
	go(all);
}

Compilation message

park.cpp:12:12: warning: 'Place' defined but not used [-Wunused-variable]
   12 | static int Place[1400];
      |            ^~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 10 ms 320 KB Output is correct
3 Correct 9 ms 340 KB Output is correct
4 Correct 9 ms 344 KB Output is correct
5 Correct 9 ms 340 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 712 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 80 ms 664 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 16 ms 664 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 824 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -