제출 #1209072

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209072		mychecksedad	Park (JOI17_park)	C++20	77 / 100	283 ms	24296 KiB

park

/* Author : Mychecksdead  */
#include "park.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
#define ff first
#define ss second
#define pii pair<int,int>
#define vi vector<int>
const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30;

static int Place[1400];

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng(34236234);
map<pii, bool> VIS;
int rn(int l, int r){
	return uniform_int_distribution<int>(l,r)(rng);
}
int n;
bool ask(int a, int b, vi u){
	for(int i = 0; i < n; ++i) Place[i] = 0;
	if(a > b) swap(a, b);
	Place[a] = 1;
	Place[b] = 1;
	for(int x: u) Place[x] = 1;
	return Ask(a, b, Place);
}
bool ask2(int a, int b, vi u){
	for(int i = 0; i < n; ++i) Place[i] = 1;
	for(int x: u) Place[x] = 0;
	if(a > b) swap(a, b);
	return Ask(a, b, Place);
}
bool ask3(int a, int b, vi u, vi u2){
	for(int i = 0; i < n; ++i) Place[i] = 0;
	for(int x: u2) Place[x] = 1;
	for(int x: u) Place[x] = 0;
	if(a > b) swap(a, b);
	Place[a] = Place[b] = 1;
	return Ask(a, b, Place);
}
vi g[N];
void answer(int a, int b){
	if(a>b) swap(a, b);
	if(VIS[{a, b}]) return;
	// cerr << a << ' ' << b << '\n';
	g[a].pb(b);
	g[b].pb(a);
	VIS[{a, b}] = 1;
	Answer(a, b);
}
void answer2(int a, int b){
	if(a>b) swap(a, b);
	if(VIS[{a, b}]) return;
	// cerr << a << ' ' << b << '\n';
	VIS[{a, b}] = 1;
	Answer(a, b);
}

vi chain_solver(vector<int> nodes){
	if(nodes.size() <= 1) return nodes;
	// cerr << "chain solve: ";
	// for(int x: nodes) cerr << x << ' ';
	// cerr << '\n';
	int v = nodes[rn(0, int(nodes.size())-1)];
	vector<vi> C;
	vector<int> U;

	for(int u: nodes){
		if(u != v){
			bool is = ask(u, v, vi{});
			if(is){
				answer(u, v);
				C.pb(vi{u});
				U.pb(u);
			}
		}
	}

	for(int u: nodes){
		bool is = 0;
		for(int x: U) is = is | (x == u);
		if(u != v && !is){
			int l = 0, r = int(U.size()) - 2, res = int(U.size()) - 1;
			while(l <= r){
				int mid = l+r>>1;
				vi to_pop;
				for(int i = 0; i <= mid; ++i) to_pop.pb(U[i]);
				if(ask3(v, u, to_pop, nodes) == 0){
					res = mid;
					r = mid - 1;
				}else{
					l = mid + 1;
				}
			}
			C[res].pb(u);
		}
	}
	vector<vi> res;
	for(auto &V: C){
		res.pb(chain_solver(V));
	}
	if(res.size() == 1){
		if(res[0].back() != U[0]) reverse(all(res[0]));
		res[0].pb(v);
		return res[0];
	}
	if(res[0].back() != U[0]) reverse(all(res[0]));
	if(res[1][0] != U[1]) reverse(all(res[1]));
	res[0].pb(v);
	for(int x: res[1]) res[0].pb(x);
	return res[0];
}

void solve(vector<int> nodes){
	if(nodes.size() <= 1) return;

	// cerr << "solve: ";
	// for(int x: nodes) cerr << x << ' ';
	// cerr << '\n';

	if(nodes.size() == 2){
		answer(nodes[0], nodes[1]);
		return;
	}

	// int v = nodes[0];//nodes[rn(0, int(nodes.size())-1)];
	int A = nodes[rn(0, int(nodes.size()) - 1)];
	int B = nodes[rn(0, int(nodes.size()) - 1)];
	while(B == A){
		B = nodes[rn(0, int(nodes.size()) - 1)];
	}

	// cerr << A << ' ' << B << '\n';

	vi cur = nodes;


	vector<vi> C;
	vector<int> U;


	while(cur.size()){
		int v = cur.back();
		cur.pop_back();
		if(v == A || v == B) continue;
		if(ask3(A, B, vi{v}, nodes) == 0){
			// its in
			C.pb({});
			U.pb(v);
		}
	}

	U = chain_solver(U);

	if(U.size()){
		if(ask(A, U[0], vi{}) == 0) reverse(all(U)), reverse(all(C));
		answer(A, U[0]);
		answer(B, U.back());
	}else{
		answer(A, B);
	}


	C.insert(C.begin(), vi{});
	U.insert(U.begin(), A);


	C.pb({});
	U.pb(B);


// 	cerr << "U :";
// 	for(int x: U) cerr << x << ' ';
// 	cerr << '\n';
// cerr << A << ' ' << B << '\n';

	for(int u: nodes){
		bool is = false;
		for(int x: U) is = is | (x == u);
		if(is) continue;
		int l = 0, r = int(U.size()) - 2, res = int(U.size()) - 1;
		while(l <= r){
			int mid = l+r>>1;
			vi to_pop = {U[mid]};
			if(ask3(B, u, to_pop, nodes)){
				l = mid + 1;
			}else{
				res = mid;
				r = mid - 1;
			}
		}
		C[res].pb(u);
	}

	for(int i = 0; i < int(U.size()); ++i){
		C[i].pb(U[i]);
	}

	for(auto V: C){
		solve(V);
	}
}

vi e, vis;
int par[N];
void dfs(int v, int p){
	e.pb(v);
	par[v] = p;
	for(int u: g[v]){
		if(u != p) dfs(u, v);
	}
}

void search(int v, vector<int> x){
	if(x.empty() || ask(v, x[0], x) == 0) return;
	int l = 0, r = int(x.size()) - 2, res = int(x.size()) - 1;
	while(l <= r){
		int mid = l+r>>1;
		vi y;
		for(int j = 0; j <= mid; ++j){
			y.pb(x[j]);
		}
		if(ask(v, y[0], y)){
			res = mid;
			r = mid - 1;
		}else l = mid + 1;
	}
	answer2(min(v, x[res]), max(v, x[res]));
	for(int j = 0; j <= res; ++j) vis[x[res]] = 1;
	for(int j = res + 1; j < x.size(); ++j){
		if(vis[par[x[j]]]){
			e.clear();
			dfs(x[j], par[x[j]]);
			search(v, e);
		}
	}
}

void Detect(int t, int nn) {
	n = nn;
	if(t == 1){
		for(int i = 0; i < n; ++i){
			for(int j = i + 1; j < n; ++j){
				if(ask(i, j, vi{})){
					answer(i, j);
				}
			}
		}
	}else{
		vi v; 
		for(int i = 1; i <= n; ++i){
			v.pb(i-1);
		}
		solve(v);

		if(t == 5){
			// cerr << "here\n";
			for(int i = 0; i < n; ++i){
				vis.clear();
				vis.resize(n + 1);
				vis[i] = 1;
				for(int u: g[i]){
					// if(u > i) continue;  // to avoid duplicate search	

					// cerr << u << ' ' << i << '\n';
					vis[u] = 1;
					for(int x: g[u]){
						if(x != i){
							// cerr << i << ' ' << x << ' ' << u << '\n';
							e.clear();
							dfs(x, u);

							search(i, e);
						}
					}
				}
			}
		}
	}
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 0 / 23