# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1116992 | hyakup | ICC (CEOI16_icc) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define bug(x) cout << #x << " " << x << endl;
const int maxn = 110;
const int logn = 8;
vector<int> pai( maxn ), componente[maxn];
int find( int a ){ return (( pai[a] == a ) ? a : pai[a] = find(pai[a]) ); }
void join( int a, int b ){
a = find(a); b = find(b);
if( a == b ) return;
for( int x : componente[b] ) componente[a].push_back(x);
pai[b] = a;
}
int get_node( vector<int>& va, vector<int>& vb ){
int a[(int)va.size()], b[(int)vb.size()], pa = 0, pb = 0;
for( int i = 0; i < va.size(); i++ ) a[pa++] = va[i];
int l = 0, r = (int)vb.size() - 1;
while( l < r ){
int mid = ( l + r )/2;
pb = 0;
for( int i = l; i <= mid; i++ ) b[pb++] = vb[i];
if( query( pa, pb, a, b ) ) r = mid;
else l = mid + 1;
}
return vb[r];
}
int a[maxn], b[maxn];
void run( int n ){
for( int i = 1; i <= n; i++ ){ pai[i] = i; componente[i].push_back(i); }
for( int i = 1; i < n; i++ ){
int pa = 0, pb = 0;
for( int k = 0; k < logn; k++ ){
pa = 0, pb = 0;
for( int cur = 1; cur <= n; cur++ ) if( pai[cur] == cur ){
for( int x : componente[cur] ){
if( (cur&(1<<k)) > 0 ) a[pa++] = x;
else b[pb++] = x;
}
}
if( query( pa, pb, a, b ) ) break;
}
vector<int> va(pa), vb(pb);
for( int i = 0; i < pa; i++ ) va[i] = a[i];
for( int i = 0; i < pb; i++ ) vb[i] = b[i];
int x = get_node( va, vb ), y = get_node( vb, va );
setRoad( x, y );
join( x, y );
}
}
int main(){ /////// para testar
int n; cin >> n;
run( n );
}