#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 110
mt19937 rng(19938);
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll pr[maxn], f[maxn];
set<ll> cc[maxn];
ll N, A, B;
ll find(ll x) {
if (x == pr[x]) return x;
return pr[x] = find(pr[x]);
}
bool same(ll a, ll b) {
return (find(a) == find(b));
}
void onion(ll a, ll b) {
a = find(a); b = find(b);
if (cc[a].size() < cc[b].size()) {
swap(a, b); swap(cc[a], cc[b]);
}
pr[b] = a;
for (auto u : cc[b]) cc[a].insert(u);
cc[b].clear();
}
/* ll query(ll sza, ll szb, ll a[], ll b[]) {
// cout << "query" << nl;
ll i, x = 0, y = 0;
for (i = 0; i < sza; i++) {
if (a[i] == A || a[i] == B) x++;
// cout << a[i] << ' ';
}
// cout << nl;
for (i = 0; i < szb; i++) {
if (b[i] == A || b[i] == B) y++;
// cout << b[i] << ' ';
}
// cout << nl;
// cout << (x == 1 && y == 1) << nl;
return (x == 1 && y == 1);
}
void setRoad(ll a, ll b) {
// cout << "set_road " << a _ b << nf;
if (a < b) swap(a, b);
if (A < B) swap(A, B);
if (a == A && b == B) cout << "correct " << a _ b << nf;
else cout << "wrong" << nf;
onion(a, b);
} */
ll split(ll l, ll r) {
// cout << "split " << l _ r << nl;
ll i, cr = 0, tt = 0;
if (l > r) return l;
for (i = l; i <= r; i++) {
if (pr[f[i]] != f[i]) continue;
tt += cc[f[i]].size();
}
for (i = l; i <= r; i++) {
if (pr[f[i]] != f[i]) continue;
if (2 * cr + cc[f[i]].size() >= tt) {
// cout << i << nl;
return i;
}
cr += cc[f[i]].size();
}
// cout << r << nl;
return r;
}
void build1(vector<array<ll, 2>> v, vector<ll> &va, vector<ll> &vb, ll bsm) {
ll i;
for (i = 0; i <= bsm; i++) {
k = split(v[i][0], v[i][1]);
for (j = v[i][0]; j <= v[i][1]; j++) {
if (pr[f[j]] != f[j]) continue;
for (auto u : cc[f[j]]) {
if (j < k) va.pb(u);
else vb.pb(u);
}
}
}
}
void build2(ll l0, ll l1, ll l2, ll r0, ll r1, ll r2, vector<ll> &va, vector<ll> &vb) {
ll i;
for (i = l0; i <= l1; i++) {
if (pr[f[i]] != f[i]) continue;
for (auto u : cc[f[i]]) {
if (l2 <= 0) break;
va.pb(u); l2--;
}
}
for (i = r0; i <= r1; i++) {
if (pr[f[i]] != f[i]) continue;
for (auto u : cc[f[i]]) {
if (r2 <= 0) break;
vb.pb(u); r2--;
}
}
}
void solve3(ll l0, ll l1, ll r0, ll r1) {
// cout << "solve3 " << l0 _ l1 _ r0 _ r1 << nf;
ll i, bsl, bsm, bsu, z, w;
bsl = 1; bsu = 0;
for (i = l0; i <= l1; i++) {
if (pr[f[i]] == f[i]) bsu += cc[f[i]].size();
}
while (bsl != bsu) {
bsm = (bsl + bsu) / 2;
vector<ll> va, vb;
build2(l0, l1, bsm, r0, r1, INF, va, vb);
int a[va.size()], b[vb.size()];
for (i = 0; i < va.size(); i++) a[i] = va[i];
for (i = 0; i < vb.size(); i++) b[i] = vb[i];
if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
else bsl = bsm + 1;
}
z = bsl;
bsl = 1; bsu = 0;
for (i = r0; i <= r1; i++) {
if (pr[f[i]] == f[i]) bsu += cc[f[i]].size();
}
while (bsl != bsu) {
bsm = (bsl + bsu) / 2;
vector<ll> va, vb;
build2(l0, l1, INF, r0, r1, bsm, va, vb);
int a[va.size()], b[vb.size()];
for (i = 0; i < va.size(); i++) a[i] = va[i];
for (i = 0; i < vb.size(); i++) b[i] = vb[i];
if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
else bsl = bsm + 1;
}
w = bsl;
vector<ll> vc, vd;
build2(l0, l1, z, r0, r1, w, vc, vd);
// cout << "set ready " << vc.back() _ vd.back() << nl;
merge(vc.back(), vd.back());
setRoad(vc.back(), vd.back());
}
void solve2(vector<array<ll, 2>> v) {
// cout << "solve2" << nf;
ll i, bsl, bsm, bsu;
bsl = 0; bsu = (ll)v.size() - 1;
while (bsl != bsu) {
bsm = (bsl + bsu) / 2;
vector<ll> va, vb;
build1(v, va, vb, bsm);
int a[va.size()], b[vb.size()];
for (i = 0; i < va.size(); i++) a[i] = va[i];
for (i = 0; i < vb.size(); i++) b[i] = vb[i];
if (query(va.size(), vb.size(), a, b) == 1) bsu = bsm;
else bsl = bsm + 1;
}
k = split(v[bsl][0], v[bsl][1]);
solve3(v[bsl][0], k - 1, k, v[bsl][1]);
}
void solve1(vector<array<ll, 2>> v) {
// cout << "solve1" << nf;
ll i;
vector<array<ll, 2>> w;
for (auto u : v) {
ll mid = split(u[0], u[1]);
w.pb({u[0], mid - 1}); w.pb({mid, u[1]});
}
vector<ll> va, vb;
build1(v, va, vb, (ll)v.size() - 1);
int a[va.size()], b[vb.size()];
for (i = 0; i < va.size(); i++) a[i] = va[i];
for (i = 0; i < vb.size(); i++) b[i] = vb[i];
if (query(va.size(), vb.size(), a, b) == 0) solve1(w);
else solve2(v);
}
void run(int N) {
/* #if !ONLINE_JUDGE && !EVAL
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
cin >> n; */
n = N;
for (i = 1; i <= n; i++) {
pr[i] = i; cc[i].insert(i); f[i] = i;
}
for (i = 1; i <= n - 1; i++) {
// cin >> A >> B;
// cout << "i = " << i << nf;
shuffle(f + 1, f + n + 1, rng);
solve1({{1, n}});
}
}
/* int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#if !ONLINE_JUDGE && !EVAL
ifstream cin("input.txt");
ofstream cout("output.txt");
#endif
cin >> N;
run(N);
} */
Compilation message
icc.cpp: In function 'long long int split(long long int, long long int)':
icc.cpp:79:38: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
79 | if (2 * cr + cc[f[i]].size() >= tt) {
| ~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~
icc.cpp: In function 'void solve3(long long int, long long int, long long int, long long int)':
icc.cpp:134:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | for (i = 0; i < va.size(); i++) a[i] = va[i];
| ~~^~~~~~~~~~~
icc.cpp:135:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | for (i = 0; i < vb.size(); i++) b[i] = vb[i];
| ~~^~~~~~~~~~~
icc.cpp:152:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for (i = 0; i < va.size(); i++) a[i] = va[i];
| ~~^~~~~~~~~~~
icc.cpp:153:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | for (i = 0; i < vb.size(); i++) b[i] = vb[i];
| ~~^~~~~~~~~~~
icc.cpp:163:31: error: no matching function for call to 'merge(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, __gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&)'
163 | merge(vc.back(), vd.back());
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from icc.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter)'
4944 | merge(_InputIterator1 __first1, _InputIterator1 __last1,
| ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4944:5: note: template argument deduction/substitution failed:
icc.cpp:163:31: note: candidate expects 5 arguments, 2 provided
163 | merge(vc.back(), vd.back());
| ^
In file included from /usr/include/c++/10/algorithm:62,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from icc.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: candidate: 'template<class _IIter1, class _IIter2, class _OIter, class _Compare> _OIter std::merge(_IIter1, _IIter1, _IIter2, _IIter2, _OIter, _Compare)'
4995 | merge(_InputIterator1 __first1, _InputIterator1 __last1,
| ^~~~~
/usr/include/c++/10/bits/stl_algo.h:4995:5: note: template argument deduction/substitution failed:
icc.cpp:163:31: note: candidate expects 6 arguments, 2 provided
163 | merge(vc.back(), vd.back());
| ^
In file included from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from icc.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator, class _Compare> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator, _Compare)'
412 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
| ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:412:1: note: template argument deduction/substitution failed:
icc.cpp:163:31: note: candidate expects 7 arguments, 2 provided
163 | merge(vc.back(), vd.back());
| ^
In file included from /usr/include/c++/10/algorithm:74,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
from icc.cpp:1:
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _ForwardIterator> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2> std::merge(_ExecutionPolicy&&, _ForwardIterator1, _ForwardIterator1, _ForwardIterator2, _ForwardIterator2, _ForwardIterator)'
417 | merge(_ExecutionPolicy&& __exec, _ForwardIterator1 __first1, _ForwardIterator1 __last1, _ForwardIterator2 __first2,
| ^~~~~
/usr/include/c++/10/pstl/glue_algorithm_defs.h:417:1: note: template argument deduction/substitution failed:
icc.cpp:163:31: note: candidate expects 6 arguments, 2 provided
163 | merge(vc.back(), vd.back());
| ^
icc.cpp: In function 'void solve2(std::vector<std::array<long long int, 2> >)':
icc.cpp:177:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for (i = 0; i < va.size(); i++) a[i] = va[i];
| ~~^~~~~~~~~~~
icc.cpp:178:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | for (i = 0; i < vb.size(); i++) b[i] = vb[i];
| ~~^~~~~~~~~~~
icc.cpp: In function 'void solve1(std::vector<std::array<long long int, 2> >)':
icc.cpp:201:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
201 | for (i = 0; i < va.size(); i++) a[i] = va[i];
| ~~^~~~~~~~~~~
icc.cpp:202:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
202 | for (i = 0; i < vb.size(); i++) b[i] = vb[i];
| ~~^~~~~~~~~~~
