#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///CEOI 2016 day 1
#include "icc.h"
/*
int query(int size_a, int size_b, int a[], int b[]){
cout<<size_a<<" : ";
f(i,0,size_a){
cout<<a[i]<<" ";
}
cout<<"\n";
cout<<size_b<<" : ";
f(i,0,size_b){
cout<<b[i]<<" ";
}
cout<<"\n";
ll v;
cin>>v;
return v;
}
*/
ll par[1005];
ll find_par(ll a){
if(par[a] == a){
return a;
}
return par[a] = find_par(par[a]);
}
void enose(ll a,ll b){
a = find_par(a);
b = find_par(b);
par[a] = b;
}
void run(int N){
ll n = N;
f(i,0,n+5){
par[i] = i;
}
while(1){
ll a = -1,b = -1;
set<ll>com;
vll exo[n+5];
vll arr;
f(i,1,n+1){
exo[find_par(i)].pb(i);
com.insert(find_par(i));
}
for(auto x:com){
arr.pb(x);
}
vll AA,BB;
set<ll>lathos[n+5];
while(1){
vll A[2];
f(i,0,arr.size()){
A[i % 2].pb(arr[i]);
}
arr = A[0];
for(auto x:A[1]){
arr.pb(x);
}
vll nA,nB;
for(auto x:A[0]){
for(auto y:exo[x]){
nA.pb(y);
}
}
for(auto x:A[1]){
for(auto y:exo[x]){
nB.pb(y);
}
}
ll sa = nA.size();
ll sb = nB.size();
ll aa[sa],bb[sb];
f(i,0,sa){
aa[i] = nA[i];
}
f(i,0,sb){
bb[i] = nB[i];
}
if(query(sa,sb,aa,bb) == 1){
AA = nA;
BB = nB;
break;
}
else{
for(auto x:A[0]){
for(auto y:A[1]){
lathos[x].insert(y);
lathos[y].insert(x);
}
}
}
}
ll l = 0,r = AA.size() - 1;
ll pos = r + 1;
while(l <= r){
ll mid = (l+r)/2;
ll sa = AA.size();
ll sb = BB.size();
ll aa[mid+1],bb[sb];
f(i,0,mid+1){
aa[i] = AA[i];
}
f(i,0,sb){
bb[i] = BB[i];
}
if(query(mid+1,sb,aa,bb) == 1){
r = mid - 1;
pos = min(pos,mid);
}
else{
l = mid + 1;
}
}
a = AA[pos];
vll C;
for(auto x:BB){
if(!lathos[find_par(a)].count(find_par(x))){
C.pb(x);
}
}
BB = C;
l = 0,r = BB.size() - 2;
pos = r + 1;
while(l <= r){
ll mid = (l+r)/2;
ll sa = AA.size();
ll sb = BB.size();
ll aa[sa],bb[mid+1];
f(i,0,sa){
aa[i] = AA[i];
}
f(i,0,mid+1){
bb[i] = BB[i];
}
if(query(sa,mid+1,aa,bb) == 1){
r = mid - 1;
pos = min(pos,mid);
}
else{
l = mid + 1;
}
}
b = BB[pos];
setRoad(a,b);
enose(a,b);
}
}
/*
int main(){
run(4);
}
*/
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:8:37: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define f(i,a,b) for(ll i = a;i < b;i++)
......
76 | f(i,0,arr.size()){
| ~~~~~~~~~~~~~~
icc.cpp:76:17: note: in expansion of macro 'f'
76 | f(i,0,arr.size()){
| ^
icc.cpp:121:20: warning: unused variable 'sa' [-Wunused-variable]
121 | ll sa = AA.size();
| ^~
icc.cpp:151:20: warning: unused variable 'sb' [-Wunused-variable]
151 | ll sb = BB.size();
| ^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
468 KB |
Ok! 100 queries used. |
| 2 |
Correct |
5 ms |
432 KB |
Ok! 99 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
32 ms |
576 KB |
Ok! 517 queries used. |
| 2 |
Correct |
50 ms |
608 KB |
Ok! 592 queries used. |
| 3 |
Correct |
44 ms |
596 KB |
Ok! 575 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
153 ms |
1064 KB |
Ok! 1352 queries used. |
| 2 |
Correct |
186 ms |
964 KB |
Ok! 1410 queries used. |
| 3 |
Correct |
168 ms |
972 KB |
Ok! 1395 queries used. |
| 4 |
Correct |
160 ms |
940 KB |
Ok! 1333 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
155 ms |
968 KB |
Ok! 1312 queries used. |
| 2 |
Correct |
190 ms |
968 KB |
Ok! 1308 queries used. |
| 3 |
Correct |
193 ms |
960 KB |
Ok! 1421 queries used. |
| 4 |
Correct |
138 ms |
956 KB |
Ok! 1307 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
233 ms |
980 KB |
Ok! 1411 queries used. |
| 2 |
Correct |
190 ms |
964 KB |
Ok! 1408 queries used. |
| 3 |
Correct |
191 ms |
960 KB |
Ok! 1422 queries used. |
| 4 |
Correct |
264 ms |
956 KB |
Ok! 1439 queries used. |
| 5 |
Correct |
150 ms |
940 KB |
Ok! 1334 queries used. |
| 6 |
Correct |
185 ms |
960 KB |
Ok! 1394 queries used. |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
192 ms |
960 KB |
Ok! 1417 queries used. |
| 2 |
Correct |
196 ms |
964 KB |
Ok! 1388 queries used. |
