Submission #983629

#TimeUsernameProblemLanguageResultExecution timeMemory
983629FZ_MeloICC (CEOI16_icc)C++14
0 / 100
1 ms348 KiB
#include "icc.h" #include <bits/stdc++.h> using namespace std; int n, tam1, tam2, c1, c2; int arr1[101], arr2[101]; set<int> componentes; vector<vector<int>> nums; int buscaComp1(vector<int> &comp1, 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(vector<int> &comp2){ 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]; } void buscaComp(vector<int> &comp1, vector<int> &comp2){ int p1=0, p2=0; if(c1!=-1) return; for(int x: nums[comp1[0]]) arr1[p1++]=x; for(int x: nums[comp2[0]]) arr2[p2++]=x; if(query(p1, p2, arr1, arr2)){ c1=buscaComp1(comp1, comp2.size()); c2=buscaComp2(comp2); return; } vector<int> aux1, aux2, aux3, aux4; int t=comp1.size(), cnt=0; for(int x: comp1){ if(cnt<t/2) aux1.push_back(x); else aux2.push_back(x); cnt++; } cnt=0; t=comp2.size(); for(int x: comp2){ if(cnt<t/2) aux3.push_back(x); else aux4.push_back(x); cnt++; } if(comp1.size()>1) buscaComp(aux1, aux2); if(comp2.size()>1) buscaComp(aux3, aux4); } int buscaNode1(){ 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 l=0, r=nums[c2].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++]=arr2[i]; } if(query(nums[c1].size(), pos, arr1, aux)) r=mid; else l=mid+1; } return arr2[l]; } pair<int, int> buscaNode(){ /*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(); b=buscaNode2(); 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(); 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++){ int cnt=0; int t=componentes.size(); vector<int> comp1, comp2; for(int x: componentes){ if(cnt<t/2) comp1.push_back(x); else comp2.push_back(x); } buscaComp(comp1, comp2); pair<int, int> node=buscaNode(); setRoad(node.first, node.second); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...