#include "park.h" #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define ll long long #define ld long double #define ull unsigned long long #define ff first #define ss second #define pii pair<int,int> #define pll pair<long long, long long> #define vi vector<int> #define vl vector<long long> #define pb push_back #define rep(i, b) for(int i = 0; i < (b); ++i) #define rep2(i,a,b) for(int i = a; i <= (b); ++i) #define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c) #define count_bits(x) __builtin_popcountll((x)) #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define forall(it,x) for(auto& it:(x)) using namespace __gnu_pbds; using namespace std; typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set; mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());} ll los(ll a, ll b) {return a + (mt() % (b-a+1));} const int INF = 1e9+50; const ll INF_L = 1e18+40; const ll MOD = 1e9+7; int is_in[1401]; vi graph[1401]; int n; vi cur_tree; vi rest; vi ls; bool odw[1401]; void dfs(int v) { odw[v] = 1; ls.pb(v); forall(it,graph[v]) { if(!odw[it]) dfs(it); } } void calc_ls(int a, vi not_use = {}) { rep(i,n) odw[i] = 0; forall(it,not_use) odw[it] = 1; ls = {}; dfs(a); } bool query(int a, int b, vi x) { rep(i,n) is_in[i] = 0; is_in[a] = 1; is_in[b] = 1; if(a > b) swap(a,b); forall(it,x) is_in[it] = 1; return Ask(a,b,is_in); } void make_path(int a, int b) { if(a == b) return; int l = -1; int r = siz(rest)-1; int r2 = -2; while(l <= r) { int mid = (l+r)/2; vi q; rep2(i,0,mid) q.pb(rest[i]); if(!query(a,b,q)) { r2 = mid; l = mid+1; } else { r = mid-1; } } r2++; int new_a; if(r2 == -1) new_a = b; else new_a = rest[r2]; if(new_a == b) { graph[a].pb(b); graph[b].pb(a); } if(new_a != b) { cur_tree.pb(new_a); swap(rest[r2],rest[siz(rest)-1]); rest.pop_back(); make_path(new_a,b); make_path(a,new_a); } } int rep_[1401]; int fint(int v) { if(v == rep_[v]) return v; return rep_[v] = fint(rep_[v]); } void onion(int a, int b) { rep_[fint(a)] = fint(b); } void comp_rek(int v, int a) { calc_ls(a,graph[v]); if(!query(v,a,ls)) return; int l = 0; int r = siz(ls)-2; int ans = siz(ls)-1; while(l <= r) { int mid = (l+r)/2; vi q; rep(i,mid+1) q.pb(ls[i]); if(query(v,a,q)) { ans = mid; r = mid-1; } else { l = mid+1; } } a = ls[ans]; graph[v].pb(a); graph[a].pb(v); rep(i,n) { rep_[i] = i; is_in[i] = 0; } forall(it,graph[v]) is_in[it] = 1; is_in[v] = 1; rep(i,n) forall(it,graph[i]) if(!is_in[i] && !is_in[it]) onion(i,it); set<int> dif; forall(it,graph[a]) if(!is_in[it]) dif.insert(fint(it)); forall(it,dif) comp_rek(v,it); } void Detect(int T, int N) { random_start(); mt.seed(2137); n = N; rep(i,n) graph[i] = {}; cur_tree = {0}; rest = {}; rep2(i,1,n-1) rest.pb(i); shuffle(all(rest),mt); while(siz(cur_tree) != n) { int ind_b = los(0,siz(rest)-1); int b = rest[ind_b]; calc_ls(0); int l = 0; int r = siz(ls)-1; int root = -1; while(l <= r) { int mid = (l+r)/2; vi q; rep(i,mid+1) q.pb(ls[i]); forall(it,rest) q.pb(it); if(!query(0,b,q)) { root = mid; l = mid+1; } else { r = mid-1; } } root++; vi tree_; swap(rest[ind_b],rest[siz(rest)-1]); rest.pop_back(); rep(i,root+1) tree_.pb(ls[i]); make_path(ls[root],b); cur_tree.pb(b); } rep(v,n) { rep(i,n) { rep_[i] = i; is_in[i] = 0; } forall(it,graph[v]) is_in[it] = 1; is_in[v] = 1; rep(i,n) forall(it,graph[i]) if(!is_in[i] && !is_in[it]) onion(i,it); set<int> dif; forall(it,graph[v]) { forall(it2,graph[it]) { if(!is_in[it2]) dif.insert(fint(it2)); } } forall(it,dif) comp_rek(v,it); } rep(i,n) forall(it,graph[i]) if(it > i) Answer(i,it); }