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;
int n, tam1, tam2;
vector<int> comp1;
vector<int> comp2;
vector<int> comp3;
int arr1[101], arr2[101];
set<int> componentes;
vector<vector<int>> nums;
int buscaComp1(int t2){
int l=0, r=comp1.size()-1;
int aux[101];
while(l<r){
int mid=(l+r)/2;
int pos=0;
for(int i=l; i<=mid; i++){
for(int x: nums[comp1[i]]){
aux[pos++]=x;
}
}
if(query(pos, t2, aux, arr2))
r=mid;
else
l=mid+1;
}
int p1=0;
for(int x: nums[comp1[l]]){
arr1[p1++]=x;
}
tam1=nums[comp1[l]].size();
return comp1[l];
}
int buscaComp2(){
int l=0, r=comp2.size()-1;
int aux[101];
while(l<r){
int mid=(l+r)/2;
int pos=0;
for(int i=l; i<=mid; i++){
for(int x: nums[comp2[i]]){
aux[pos++]=x;
}
}
if(query(tam1, pos, arr1, aux))
r=mid;
else
l=mid+1;
}
int p2=0;
for(int x: nums[comp2[l]]){
arr2[p2++]=x;
}
tam2=nums[comp2[l]].size();
return comp2[l];
}
pair<int, int> buscaComp(){
int p1=0, p2=0;
int t=componentes.size(), cnt=0;
int a, b;
comp1.clear();
comp2.clear();
comp3.clear();
for(int it: componentes){
if(cnt<t/2){
for(int x: nums[it])
arr1[p1++]=x;
comp1.push_back(it);
}
else{
for(int x: nums[it])
arr2[p2++]=x;
comp2.push_back(it);
}
cnt++;
}
if(query(p1, p2, arr1, arr2)){
a=buscaComp1(p2);
b=buscaComp2();
}
else{
p1=p2=0;
cnt=0;
comp3=comp1;
t=comp3.size();
comp1.clear();
comp2.clear();
for(int c: comp3){
if(cnt<t/2){
for(int x: nums[c]){
arr1[p1++]=x;
}
comp1.push_back(c);
}
else{
for(int x: nums[c]){
arr2[p2++]=x;
}
comp2.push_back(c);
}
cnt++;
}
if(query(p1, p2, arr1, arr2)){
a=buscaComp1(p2);
b=buscaComp2();
}
else{
p1=p2=0;
cnt=0;
comp1.clear();
comp2.clear();
comp3.clear();
t=componentes.size();
for(int c: componentes){
if(cnt>=t/2){
comp3.push_back(c);
}
cnt++;
}
t=comp3.size();
cnt=0;
p1=p2=0;
for(int c: comp3){
if(cnt<t/2){
for(int x: nums[c])
arr1[p1++]=x;
comp1.push_back(c);
}
else{
for(int x: nums[c])
arr2[p2++]=x;
comp2.push_back(c);
}
cnt++;
}
a=buscaComp1(p2);
b=buscaComp2();
}
}
return {a, b};
}
int buscaNode1(int c1, int c2){
int l=0, r=nums[c1].size()-1;
int aux[101];
while(l<r){
int mid=(l+r)/2;
int pos=0;
for(int i=l; i<=mid; i++){
aux[pos++]=arr1[i];
}
if(query(pos, nums[c2].size(), aux, arr2))
r=mid;
else
l=mid+1;
}
return arr1[l];
}
int buscaNode2(int a, int c2){
int l=0, r=nums[c2].size()-1;
int aux[101];
int ya[]={a};
while(l<r){
int mid=(l+r)/2;
int pos=0;
for(int i=l; i<=mid; i++){
aux[pos++]=arr2[i];
}
if(query(1, pos, ya, aux))
r=mid;
else
l=mid+1;
}
return arr2[l];
}
pair<int, int> buscaNode(int c1, int c2){
int p1=0, p2=0;
for(int x: nums[c1]){
arr1[p1++]=x;
}
for(int x: nums[c2]){
arr2[p2++]=x;
}
int a, b;
a=buscaNode1(c1, c2);
b=buscaNode2(a, c2);
if(nums[c1].size()>=nums[c2].size()){
componentes.erase(c2);
for(int x: nums[c2]){
nums[c1].push_back(x);
}
}
else{
componentes.erase(c1);
for(int x: nums[c1]){
nums[c2].push_back(x);
}
}
return {a, b};
}
void run(int N){
n=N;
nums.clear();
componentes.clear();
comp1.clear();
comp2.clear();
comp3.clear();
nums.resize(n+1);
for(int i=1; i<=n; i++){
componentes.insert(i);
nums[i].push_back(i);
}
for(int k=0; k<n-1; k++){
pair<int, int> comp=buscaComp();
pair<int, int> node=buscaNode(comp.first, comp.second);
setRoad(node.first, node.second);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |