Submission #1212148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1212148		og_matveychick1	Park (JOI17_park)	C++20	67 / 100	491 ms	908 KiB

park

#include "park.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

// /*
//                                                //////////**DEFINES - START**//////////

#define ret return
#define fi first
#define se second
#define mp make_pair
#define all(x) x.begin(), x.end()
#define be(x) x.begin()
#define en(x) x.end()
#define sz(x) ll(x.size())
#define for0(i, n) for (ll   i = 0; i < (n); ++i)
#define for1(i, n) for (ll   i = 1; i < (n); ++i)
#define rfor0(i, n) for (ll   i = (n) - 1; i >= 0; --i)
#define rfor1(i, n) for (ll   i = (n) - 1; i >= 1; --i)
#define rep(i, a, n) for (ll   i = a; i < ll(n); ++i)
#define rrep(i, a, n) for (ll   i = a - 1; i >= ll(n); --i)
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define fastIO() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define con continue
#define pb push_back
#define pob pop_back
#define deb(x) cout << (#x) << " is " << (x) << endl
#define ins insert
#define len(s) (s).length()
#define gi greater<int>()
#define gll greater<ll  >()
#define gstr greater<string>()
#define gpll greater<pair<ll  , ll  >>()
#define rast(x1, y1, x2, y2) sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2))
#define rev reverse
#define ub upper_bound
#define lb lower_bound
#define bs binary_search
#define rs resize
#define last(a) a.back()
#define co count
#define ba(a) a.back()
#define um unordered_map
#define rsun(a) a.resize(unique(a.begin(), a.end())-a.begin())
#define endl '\n'
#ifdef OG_Matveychick1
bool local = true;
#else
bool local = false;
#endif

//                                                \\\\\\\\\\**DEFINES - END**\\\\\\\\\\
        // */

// /*
//                                                //////////**TYPEDEFS - START**//////////

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef vector<string> vs;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ull> vull;
typedef pair<ll, ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef pair<double, double> pdd;
typedef double ld;
typedef double D;
typedef vector<ld> vld;
typedef vector<pair<ld, ld>>
        vpld;
typedef string str;
typedef set<ll> sll;
typedef set<int> si;
typedef set<str> ss;
typedef set<pii> spii;
typedef multiset<int> msi;
typedef multiset<ll> msll;
typedef multiset<str> mss;
typedef multiset<pii> mspii;
typedef multiset<pll> mspll;
typedef map<str, str> mps;
typedef map<int, int> mpi;
typedef map<ll, ll> mpll;
typedef map<int, vi> mpvi;
typedef map<int, vll> mpvll;
typedef map<char, int> mpci;
typedef multimap<ll, ll> mmpll;
typedef multimap<str, str> mmps;
typedef multimap<int, int> mmpi;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef vector<vector<long double>> vvld;
typedef vector<vvi> vvvi;
typedef vector<vector<char>> vvc;
typedef vector<vs> vvs;
typedef vector<D> vD;
typedef set<pair<ll, ll>>
        spll;
typedef pair<ull, ull> pull;
typedef vector<pull> vpull;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef set<char> sc;
typedef queue<int> qi;
typedef queue<ll> qll;
typedef queue<bool> qb;
typedef vector<sll> vsll;
typedef queue<pair<ll, ll>>
        qpll;
typedef vector<vector<pair<int, int>>>
        vvpii;
typedef vector<vector<pair<ll, ll>>>
        vvpll;
typedef vector<spll> vspll;
typedef multiset<char> msc;
typedef queue<str> qs;
typedef vector<set<int>> vsi;
typedef priority_queue<ll> pqll;
typedef vector<vsll> vvsll;
typedef pair<ld, ld> pld;
typedef vector<vvll> vvvll;
typedef set<ld> sld;
typedef vector<vpld> vvpld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
        ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update>
        ordered_multiset;

//                                                \\\\\\\\\\**TYPEDEFS - END**\\\\\\\\\\
        // */


// /*
//                                                //////////**CONSTANTS - START**//////////

const ld pi = acosl(-1);
const ll mod1 = 1e9 + 7;
const ll mod2 = 998244353;
const ll MAXLL = 9223372036854775807;
//const ll MAXINT = 2147483647;
const ld eps = 1e-6;

//                                                \\\\\\\\\\**CONSTANTS - END**\\\\\\\\\\
        // */


// /*
//                                                //////////**TEMPLATES - START**//////////


template<typename T>
istream &operator>>(istream &in, vector<T> &a) {
    for (T &i: a) in >> i;
    return in;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, pair<T1, T2> &a) {
    in >> a.fi >> a.se;
    return in;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, pair<T1, T2> &a) {
    out << a.fi << " " << a.se;
    return out;
}

template<typename T1, typename T2>
istream &operator>>(istream &in, vector<pair<T1, T2>>

&a) {
    for (
        pair<T1, T2> &i
            : a)
        in >> i.fi >> i.
                se;
    return
            in;
}

template<typename T>
ostream &operator<<(ostream &out, const vector<T> &a) {
    for (auto i: a) {
        out << i << " ";
    }
    return out;
}

template<typename T1, typename T2>
ostream &operator<<(ostream &out, vector<pair<T1, T2>>

&a) {
    for (
        pair<T1, T2> i
            : a)
        out << i.fi << " " << i.se <<
            endl;
    return
            out;
}

template<typename T1>
ostream &operator<<(ostream &out, vector<vector<T1>> &a) {
    for (vector<T1> i: a) {
        for (T1 j: i) out << j << " ";
        out << endl;
    }
    return out;
}

template<typename T1, typename T2>
inline T1 min(T1 a, T2 b) {
    b = (T1) b;
    return a > b ? b : a;
}

template<typename T1, typename T2>
inline T1 max(T1 a, T2 b) {
    b = (T1) b;
    return a > b ? a : b;
}

template<typename T1, typename T2>
inline void amin(T1 &a, T2 b) {
    a = min(a, b);
}

template<typename T1, typename T2>
inline void amax(T1 &a, T2 b) {
    a = max(a, b);
}


//                                                \\\\\\\\\\**TEMPLATES - END**\\\\\\\\\\
        // */


// This bear is a good alternative to duck!!!
/*
    ????      ??????
  ???????????????????
 ????????????????  ???
???   ???????????  ???
???  ???????????? ??
 ??????????????????
   ??????????????? ?
   ?????????????????
   ???????   ???    ??
    ????  ??????????
     ????     ?? ???
   ???????????? ?????
  ????????????????????
 ????????   ??  ???????
 ???????         ?????
 */


ld getTime() {
    return (ld) clock() / (ld) CLOCKS_PER_SEC;
}


//mt19937_64 rn(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rn(0);

ll rnd(ll l, ll r) {
    ll a = rn() % (r - l + 1) + l;
    return a;
}


const ll N = 1400;

bool fl = 1;
ll n;
vll g[N];
spll s;

void ans(ll a, ll b) {
    if (a > b) swap(a, b);
    if (a == 1 && b == 7) {
        bool fl = 0;
    }
    if (s.find({a, b}) != en(s)) ret;
    s.ins({a, b});
    if (fl) {
        g[a].pb(b);
        g[b].pb(a);
    }
    Answer(a, b);
}

bool ask(int a, int b, int *p) {
    ret Ask(min(a, b), max(a, b), p);
}

bool c1(ll l, ll r, vll v1, vll v2) {
    int p[n];
    memset(p, 0, sizeof p);
    p[l] = p[r] = 1;
    for (auto x: v1) p[x] = 1;
    for (auto x: v2) p[x] = 1;
    ret ask(l, r, p);
}

bool c3(ll l, ll r, vll v1, vll v2) {
    int p[n];
    fill(p, p + n, 0);
    p[l] = p[r] = 1;
    for (auto x: v1) p[x] = 1;
    for (auto x: v2) p[x] = 1;
    ret ask(l, r, p);
}

map<ll, vll> ma;

void go2(ll l, ll r, vll a) {
    if (sz(a) == 1) {
        go2(l, a[0], {});
        go2(a[0], r, {});
        ret;
    }
    if (!sz(a)) {
        ans(l, r);
        ma[l].pb(r);
        ma[r].pb(l);
        ret;
    }
//    shuffle(all(a), rn);
    ll x = a[sz(a) / 2];
    vll L, R;
    a.erase(find(all(a), x));
    while (sz(a)) {
        ll c = ba(a);
        a.pob();
        if (!c1(l, x, L, a)) L.pb(c);
        else R.pb(c);
    }
    go2(l, x, L);
    go2(x, r, R);
}

bool c2(ll u, ll v, vll a, vll pt, ll l, ll r) {
    int p[n];
    fill(p, p + n, 0);
    p[u] = p[v] = 1;
    for (auto x: a) p[x] = 1;
    for (auto x: pt) p[x] = 0;
    rep(i, l, r) p[pt[i]] = 1;
    return ask(u, v, p);
}

void go1(ll v, vll a) {
    if (!sz(a)) ret;
//    shuffle(all(a), rn);
    ll x = a[sz(a) / 2];
    a.erase(find(all(a), x));
    vll a1 = a, a2;
    while (sz(a1)) {
        ll c = ba(a1);
        a1.pob();
        if (!c3(v, x, a1, a2)) a2.pb(c);
    }
    go2(v, x, a2);
    vll pt{v};
    ll u = v, p = -1;
    while (1) {
        ll nxt = -1;
        for (auto c: ma[u]) {
            if (c != p) nxt = c;
        }
        if (nxt == -1) break;
        p = u;
        u = nxt;
        pt.pb(u);
    }
    ma.clear();
    for1(i, sz(pt) - 1) a.erase(find(all(a), pt[i]));
    vvll b(sz(pt));
    for (auto c: a) {
        ll l = 0, r = sz(pt);
        while (l + 1 < r) {
            ll m = (l + r) / 2;
            (c2(pt[m], c, a, pt, m, r) ? l : r) = m;
        }
        b[l].pb(c);
    }
    for0(i, sz(pt)) go1(pt[i], b[i]);
}

vll pt;

bool c4(ll v, vll a) {
    int p[n];
    fill(p, p + n, 0);
    p[v] = 1;
    for (auto x: a) p[x] = 1;
    ret ask(v, a[0], p);
}

void go3(ll v, vll a) {
    if (!sz(a)) ret;
    if (!c4(v, a)) ret;
    if (sz(a) == 1) {
        ans(v, a[0]);
        ret;
    }
    ll m = sz(a) / 2;
    vll l, r;
    for0(i, sz(a)) (i < m ? l : r).pb(a[i]);
    go3(v, l);
    go3(v, r);
}

void dfs(ll v, ll p) {

    if (sz(pt)) {
        ll k = ba(pt);
        pt.pob();
        go3(v, pt);
        pt.pb(k);
    }
    pt.pb(v);
    for (auto x: g[v]) {
        if (x == p) con;
        dfs(x, v);
    }
    pt.pob();
}

void Detect(int T, int _n) {
    n = _n;

    vll a(n - 1);
    iota(all(a), 1);
    go1(0, a);

    fl = 0;
    dfs(0, 0);
}

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