#include <bits/stdc++.h>
#include "icc.h"
#define loop(i, a, b) for(long long i=a;i<b;i++)
#define pool(i, a, b) for(long long i=a-1;i>=b;i--)
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define vc vector
#define pa pair<ll, ll>
#define ll long long
#define all(a) a.begin(), a.end()
using namespace std;
#define mn 1000010
#define pa pair<ll, ll>
#define ld long double
vc<vc<ll>> dsu;
int aA[105], aB[105];
ll quer(int sa, int sb, vc<ll> a, vc<ll> b){
loop(i, 0, sa) aA[i]=a[i];
loop(i, 0, sb) aB[i]=b[i];
return query(sa, sb, aA, aB);
}
ll dsuque(vc<ll> a, vc<ll> b){
vc<ll> qa, qb;
fore(v, a) fore(u, dsu[v]) qa.ps(u);
fore(v, b) fore(u, dsu[v]) qb.ps(u);
return quer(qa.size(), qb.size(), qa, qb);
}
pa solve(){
vc<ll> fa, fb;
if(dsu.size()==2){
fa.ps(0);
fb.ps(1);
}
else{
vc<pa> arr[2];
arr[0].ps(make_pair(0, dsu.size()));
while(1){
vc<pa> temp[2];
fore(v, arr[0]){
if(v.fi==v.se-1){
temp[0].ps(v);
continue;
}
ll mid=v.fi+v.se;mid/=2;
temp[0].ps(make_pair(v.fi, mid));
temp[1].ps(make_pair(mid, v.se));
}
fore(v, arr[1]){
if(v.fi==v.se-1){
temp[1].ps(v);
continue;
}
ll mid=v.fi+v.se;mid/=2;
temp[0].ps(make_pair(v.fi, mid));
temp[1].ps(make_pair(mid, v.se));
}
arr[0]=temp[0];
arr[1]=temp[1];
vc<ll> a, b;
fore(v, arr[0]) loop(i, v.fi, v.se) a.ps(i);
fore(v, arr[1]) loop(i, v.fi, v.se) b.ps(i);
if(dsuque(a, b)){
fa=a, fb=b;
break;
}
}
}
while(fa.size()>1){
vc<ll> l[2];
loop(i, 0, fa.size()) l[i%2].ps(fa[i]);
if(dsuque(l[0], fb)) fa=l[0];
else fa=l[1];
}
while(fb.size()>1){
vc<ll> l[2];
loop(i, 0, fb.size()) l[i%2].ps(fb[i]);
if(dsuque(l[0], fa)) fb=l[0];
else fb=l[1];
}
vc<ll> ta=dsu[fa[0]], tb=dsu[fb[0]];
while(ta.size()>1){
vc<ll> l[2];
loop(i, 0, ta.size()) l[i%2].ps(ta[i]);
if(quer(l[0].size(), tb.size(), l[0], tb)) ta=l[0];
else ta=l[1];
}
while(tb.size()>1){
vc<ll> l[2];
loop(i, 0, tb.size()) l[i%2].ps(tb[i]);
if(quer(l[0].size(), ta.size(), l[0], ta)) tb=l[0];
else tb=l[1];
}
return make_pair(ta[0], tb[0]);
}
void run(int n){
loop(i, 1, n+1) dsu.ps(vc<ll> {i});
loop(i, 0, n-1){
pa ans=solve();
ll a, b;vc<ll> temp;
loop(i, 0, dsu.size()) fore(u, dsu[i]) if(u==ans.fi) a=i;
fore(v, dsu[a]) temp.ps(v);
dsu.erase(dsu.begin()+a);
loop(i, 0, dsu.size()) fore(u, dsu[i]) if(u==ans.se) b=i;
fore(v, dsu[b]) temp.ps(v);
dsu.erase(dsu.begin()+b);
dsu.ps(temp);
setRoad(ans.fi, ans.se);
}
}
Compilation message
icc.cpp: In function 'std::pair<long long int, long long int> solve()':
icc.cpp:3:42: 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]
3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
73 | loop(i, 0, fa.size()) l[i%2].ps(fa[i]);
| ~~~~~~~~~~~~~~~
icc.cpp:73:9: note: in expansion of macro 'loop'
73 | loop(i, 0, fa.size()) l[i%2].ps(fa[i]);
| ^~~~
icc.cpp:3:42: 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]
3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
79 | loop(i, 0, fb.size()) l[i%2].ps(fb[i]);
| ~~~~~~~~~~~~~~~
icc.cpp:79:9: note: in expansion of macro 'loop'
79 | loop(i, 0, fb.size()) l[i%2].ps(fb[i]);
| ^~~~
icc.cpp:3:42: 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]
3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
86 | loop(i, 0, ta.size()) l[i%2].ps(ta[i]);
| ~~~~~~~~~~~~~~~
icc.cpp:86:9: note: in expansion of macro 'loop'
86 | loop(i, 0, ta.size()) l[i%2].ps(ta[i]);
| ^~~~
icc.cpp:3:42: 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]
3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
92 | loop(i, 0, tb.size()) l[i%2].ps(tb[i]);
| ~~~~~~~~~~~~~~~
icc.cpp:92:9: note: in expansion of macro 'loop'
92 | loop(i, 0, tb.size()) l[i%2].ps(tb[i]);
| ^~~~
icc.cpp: In function 'void run(int)':
icc.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
103 | loop(i, 0, dsu.size()) fore(u, dsu[i]) if(u==ans.fi) a=i;
| ~~~~~~~~~~~~~~~~
icc.cpp:103:9: note: in expansion of macro 'loop'
103 | loop(i, 0, dsu.size()) fore(u, dsu[i]) if(u==ans.fi) a=i;
| ^~~~
icc.cpp:3:42: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
3 | #define loop(i, a, b) for(long long i=a;i<b;i++)
......
107 | loop(i, 0, dsu.size()) fore(u, dsu[i]) if(u==ans.se) b=i;
| ~~~~~~~~~~~~~~~~
icc.cpp:107:9: note: in expansion of macro 'loop'
107 | loop(i, 0, dsu.size()) fore(u, dsu[i]) if(u==ans.se) b=i;
| ^~~~
icc.cpp:108:22: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized]
108 | fore(v, dsu[b]) temp.ps(v);
| ^
icc.cpp:104:22: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
104 | fore(v, dsu[a]) temp.ps(v);
| ^
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Ok! 113 queries used. |
| 2 |
Correct |
10 ms |
512 KB |
Ok! 114 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
57 ms |
512 KB |
Ok! 653 queries used. |
| 2 |
Correct |
54 ms |
512 KB |
Ok! 740 queries used. |
| 3 |
Correct |
69 ms |
568 KB |
Ok! 780 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
167 ms |
632 KB |
Ok! 1867 queries used. |
| 2 |
Correct |
168 ms |
512 KB |
Ok! 1803 queries used. |
| 3 |
Correct |
193 ms |
632 KB |
Ok! 1984 queries used. |
| 4 |
Correct |
177 ms |
632 KB |
Ok! 1895 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
179 ms |
512 KB |
Ok! 1947 queries used. |
| 2 |
Correct |
181 ms |
584 KB |
Ok! 1950 queries used. |
| 3 |
Correct |
178 ms |
512 KB |
Ok! 1997 queries used. |
| 4 |
Correct |
185 ms |
544 KB |
Ok! 1894 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
178 ms |
512 KB |
Too many queries! 1972 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
181 ms |
704 KB |
Too many queries! 1996 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
