oj.uz

답안 #969764

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
969764 2024-04-25T14:40:27 Z penguin133 Park (JOI17_park) C++17
20 / 100
 586 ms 1160 KB 
#include <bits/stdc++.h>
using namespace std;
#include "park.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

static int Place[1400], p2[1400];
const int szz = 8;
void dnc(vector <int> shit){
	if(shit.size() <= 1)return;
	if(shit.size() <= szz){
		for(int i = 0; i < (int)shit.size(); i++){
			for(int j = i + 1; j < (int)shit.size(); j++){
				int x = shit[i], y = shit[j];
				Place[x] = Place[y] = 1;
				if(x > y)swap(x, y);
				if(Ask(x, y, Place))Answer(x, y);
				Place[x] = Place[y] = 0;
			}
		}
		return;
	}
	vector <int> nxtstuff, die[7];
	int bru = shit[rng()%shit.size()];
	for(int i = 0; i < (int)shit.size(); i++){
		if(shit[i] == bru)continue;
		Place[bru] = Place[shit[i]] = 1;
		int a = bru, b = shit[i];
		if(a > b)swap(a, b);
		if(Ask(a, b, Place)){
			nxtstuff.push_back(shit[i]);
			Answer(a, b);
		}
		Place[bru] = Place[shit[i]] = 0;
	}
	for(int i = 0; i < 1400; i++)p2[i] = 0;
	for(auto i : shit)p2[i] = 1;
	for(auto i : shit){
		if(i == bru)continue;
		bool f = 0;
		for(auto j : nxtstuff)if(i == j)f = 1;
		if(f)continue;
		int lo = 0, hi = (int)nxtstuff.size() - 2, tmp = (int)nxtstuff.size() - 1;
		while(lo <= hi){
			int mid = (lo + hi) >> 1;
			for(int k = mid + 1; k < (int)nxtstuff.size(); k++)p2[nxtstuff[k]] = 0;
			int a = bru, b = i;
			if(a > b)swap(a, b);
			int res = Ask(a, b, p2);
			for(auto k : nxtstuff)p2[k] = 1;
			if(res){
				tmp = mid;
				hi = mid - 1;
			}
			else lo = mid + 1;
		}
		die[tmp].push_back(i);
	}
	for(int i = 0; i < (int)nxtstuff.size(); i++){
		die[i].push_back(nxtstuff[i]);
		dnc(die[i]);
	}
}

set <int> adj[1405];
int sz[1405], block[1405], up[1405];
vector <pi> what;
void comp(int x, int par){
	sz[x] = 1;
	up[x] = par;
	for(auto i : adj[x])if(i != par && !block[i])comp(i, x), sz[x] += sz[i];
	what.push_back({sz[x], x});
}

void Detect(int T, int N) {
	if(T == 1){
		for(int i = 0; i < N; i++){
			for(int j = i + 1; j < N; j++){
				Place[i] = Place[j] = 1;
				if(Ask(i, j, Place))Answer(i, j);
				Place[i] = Place[j] = 0;
			}
		}
		return;
	}
	/*
	vector <int> lol;
	for(int i = 0; i < N; i++)lol.push_back(i);
	shuffle(lol.begin(), lol.end(), rng);
	dnc(lol);
	*/
	vector <int> fku;
	for(int i = 1; i < N; i++)fku.push_back(i);
	shuffle(fku.begin(), fku.end(), rng);
	for(auto i : fku){
		int hd = 0, res = -1;
		for(int j = 0; j < N; j++)block[j] = 0;
		while(1){
			what.clear();
			comp(hd, -1);
			if(sz[hd] == 1){
				break;
			}
			sort(what.begin(), what.end());
			pi bruh = {sz[hd] / 2, 0};
			int tmp = lower_bound(what.begin(), what.end(), bruh) - what.begin();
			if(tmp == (int)what.size())tmp--;
			int fin = (tmp ? (abs(what[tmp].fi - sz[hd] / 2) < abs(what[tmp - 1].fi - sz[hd] / 2) ? tmp : tmp - 1) : tmp);
			fin = what[fin].se;
			for(int a = 0; a < N; a++)Place[a] = 1;
			Place[fin] = 0;
			if(Ask(0, i, Place)){
				//not in subtree
				block[fin] = 1;
			}
			else{
				hd = fin;
				if(up[fin] != -1)block[up[fin]] = 1;
			}
		}
		int repl = -1;
		vector <int> bruh;
		for(auto j : adj[hd]){
			for(int a = 0; a < N; a++)Place[a] = 1;
			Place[i] = 0;
			if(j && !Ask(0, j, Place)){
				bruh.push_back(j);
				repl = j;
			}
		}
		if(!bruh.empty()){
			for(auto a : bruh){
				adj[hd].erase(a);
				adj[a].erase(hd);
				adj[i].insert(a);
				adj[a].insert(i);
			}
			adj[hd].insert(i);
			adj[i].insert(hd);
			
		}
		else adj[hd].insert(i), adj[i].insert(hd);
	}
	for(int i = 0; i < N; i++){
		for(auto j : adj[i]){
			//cout << j << ' ';
			if(j > i)Answer(i, j);
		}
	}
}

Compilation message

park.cpp: In function 'void Detect(int, int)':
park.cpp:103:15: warning: unused variable 'res' [-Wunused-variable]
  103 |   int hd = 0, res = -1;
      |               ^~~
park.cpp:128:7: warning: variable 'repl' set but not used [-Wunused-but-set-variable]
  128 |   int repl = -1;
      |       ^~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 3 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 852 KB Output is correct
2 Correct 125 ms 852 KB Output is correct
3 Correct 126 ms 828 KB Output is correct
4 Correct 162 ms 848 KB Output is correct
5 Correct 174 ms 864 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 438 ms 604 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 254 ms 808 KB Output is correct
2 Correct 337 ms 860 KB Output is correct
3 Correct 343 ms 768 KB Output is correct
4 Correct 373 ms 852 KB Output is correct
5 Correct 317 ms 916 KB Output is correct
6 Correct 242 ms 904 KB Output is correct
7 Correct 297 ms 804 KB Output is correct
8 Correct 464 ms 1108 KB Output is correct
9 Correct 536 ms 924 KB Output is correct
10 Correct 523 ms 652 KB Output is correct
11 Correct 373 ms 848 KB Output is correct
12 Correct 452 ms 688 KB Output is correct
13 Correct 370 ms 600 KB Output is correct
14 Correct 506 ms 1108 KB Output is correct
15 Correct 319 ms 724 KB Output is correct
16 Incorrect 437 ms 1160 KB Wrong Answer[5]
17 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 586 ms 600 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -