#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define lll __int128
#define ull unsigned long long
#define fi first
#define se second
#define db double
#define ld long double
#define lld __float128
/// order_of_key, find_by_order
template<class T, class COMP>
using custom_set = tree<T, null_type, COMP, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T, class U>
using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd_64(chrono::steady_clock::now().time_since_epoch().count());
#include "icc.h"
//int query(int size_a, int size_b, int a[], int b[])
//{
// for(int i = 0; i < size_a; i++)
// {
// cout << a[i] << ' ';
// } cout << '\n';
// for(int i = 0; i < size_b; i++)
// {
// cout << b[i] << ' ';
// } cout << '\n';
// int res; cin >> res; return res;
//}
//
//void setRoad(int a, int b)
//{
// cout << a << " - " << b << '\n';
//}
int qrr(set<int> a, set<int> b)
{
int n = a.size(), m = b.size();
int A[n], B[m], i = 0;
for(auto j : a)
{
A[i++] = j+1;
}
i = 0;
for(auto j : b)
{
B[i++] = j+1;
}
if(!n || !m)
return 0;
return query(n, m, A, B);
}
const int MAXN = 1005;
int pr[MAXN], sz[MAXN], cur;
vector<int> lc[MAXN], rc[MAXN], ind[MAXN];
vector<pair<int, int> > dat;
void solve(int l, int r, int d)
{
if(l > r)
return;
int m = (l+r) / 2;
ind[d].push_back(cur);
lc[cur].clear();
rc[cur].clear();
int m1 = m, m2 = m;
while(m2 < r && dat[m2+1].fi == dat[m].fi) m2++;
while(m1 >= l && dat[m1].fi == dat[m+1].fi) m1--;
if(m1+1 == l && m2 == r)
{
cur++;
return;
}
if(m1+1 != l)
m = m1;
else
m = m2;
for(int i = l; i <= m; i++)
{
lc[cur].push_back(dat[i].se);
}
for(int i = m+1; i <= r; i++)
{
rc[cur].push_back(dat[i].se);
}
cur++;
if(l == r)
return;
solve(l, m, d+1);
solve(m+1, r, d+1);
}
int lead(int v)
{
if(v == pr[v])
return v;
return pr[v] = lead(pr[v]);
}
bool comb(int a, int b)
{
a = lead(a);
b = lead(b);
if(a == b)
return 0;
if(sz[a] > sz[b])
swap(a, b);
sz[b] += sz[a];
pr[a] = b;
return 1;
}
void run(int n)
{
for(int i = 0; i < n; i++)
{
pr[i] = i;
sz[i] = 1;
}
for(int i = 0; i < n-1; i++)
{
for(int j = 0; j < n; j++)
{
dat.push_back({lead(j), j});
ind[j].clear();
}
sort(dat.begin(), dat.end());
// for(int j = 0; j < n; j++)
// {
// cout << dat[j].se+1 << ' ';
// } cout << '\n';
cur = 0;
solve(0, n-1, 0);
dat.clear();
bool bb = 0;
for(int j = 0; j < n; j++)
{
// cout << "J" << ": " << j << '\n';
set<int> a, b, ca;
for(auto v : ind[j])
{
for(auto kk : lc[v])
{
a.insert(kk);
ca.insert(lead(kk));
}
for(auto kk : rc[v])
{
if(ca.count(lead(kk)))
a.insert(kk);
else
b.insert(kk);
}
}
if(!qrr(a, b))
continue;
int l = 0, r = ind[j].size()-1;
while(l != r)
{
int m = (l+r) / 2;
a.clear(); b.clear(); ca.clear();
for(int v = l; v <= m; v++)
{
for(auto k : lc[ind[j][v]])
{
a.insert(k);
ca.insert(lead(k));
}
for(auto k : rc[ind[j][v]])
{
if(ca.count(lead(k)))
a.insert(k);
else
b.insert(k);
}
}
if(qrr(a, b))
r = m;
else
l = m+1;
}
vector<int> le, re;
a.clear(); b.clear(); ca.clear();
int kek = ind[j][l];
for(auto v : lc[kek])
{
le.push_back(v); ca.insert(lead(v));
}
for(auto v : rc[kek])
{
if(ca.count(lead(v)))
le.push_back(v);
else
re.push_back(v);
}
l = 0; r = le.size()-1;
while(l != r)
{
int m = (l+r) / 2;
a.clear(); b.clear(); ca.clear();
for(int v = l; v <= m; v++)
{
a.insert(le[v]);
}
for(auto v : re)
{
b.insert(v);
}
if(qrr(a, b))
r = m;
else
l = m+1;
}
int L = l;
l = 0; r = re.size()-1;
while(l != r)
{
int m = (l+r) / 2;
a.clear(); b.clear(); ca.clear();
for(int v = l; v <= m; v++)
{
b.insert(re[v]);
}
for(auto v : le)
{
a.insert(v);
}
if(qrr(a, b))
r = m;
else
l = m+1;
}
int R = r;
setRoad(le[L]+1, re[R]+1);
comb(le[L], re[R]);
bb = 1;
break;
}
}
}
//
//int main()
//{
// int n; cin >> n;
// run(n);
//}
/// shche ne vmerla Ykraina
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:162:14: warning: variable 'bb' set but not used [-Wunused-but-set-variable]
bool bb = 0;
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
632 KB |
Ok! 98 queries used. |
| 2 |
Correct |
9 ms |
760 KB |
Ok! 94 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
632 KB |
Ok! 503 queries used. |
| 2 |
Correct |
42 ms |
632 KB |
Ok! 497 queries used. |
| 3 |
Correct |
42 ms |
636 KB |
Ok! 493 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
130 ms |
804 KB |
Ok! 1239 queries used. |
| 2 |
Correct |
140 ms |
632 KB |
Ok! 1232 queries used. |
| 3 |
Correct |
122 ms |
704 KB |
Ok! 1164 queries used. |
| 4 |
Correct |
132 ms |
636 KB |
Ok! 1217 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
712 KB |
Ok! 1147 queries used. |
| 2 |
Correct |
146 ms |
676 KB |
Ok! 1179 queries used. |
| 3 |
Correct |
126 ms |
632 KB |
Ok! 1150 queries used. |
| 4 |
Correct |
125 ms |
760 KB |
Ok! 1193 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
128 ms |
776 KB |
Ok! 1144 queries used. |
| 2 |
Correct |
137 ms |
688 KB |
Ok! 1204 queries used. |
| 3 |
Correct |
136 ms |
688 KB |
Ok! 1220 queries used. |
| 4 |
Correct |
135 ms |
632 KB |
Ok! 1219 queries used. |
| 5 |
Correct |
132 ms |
632 KB |
Ok! 1252 queries used. |
| 6 |
Correct |
140 ms |
760 KB |
Ok! 1254 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
760 KB |
Ok! 1198 queries used. |
| 2 |
Correct |
136 ms |
700 KB |
Ok! 1213 queries used. |
