| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 255638 | kimbj0709 | ICC (CEOI16_icc) | C++14 | 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<bits/stdc++.h>
//#include "icc.h"
using namespace std;
//#define int long long
vector<int> color(105);
vector<vector<int> > comp(105);
int q(vector<int> &a,vector<int> &b){
if(a.size()==0||b.size()==0){
return 0;
}
int aa[(int)a.size()];
int bb[(int)b.size()];
for(int i=0;i<(int)a.size();i++){
aa[i] = a[i];
}
for(int i=0;i<(int)b.size();i++){
bb[i] = b[i];
}
/*for(auto k:a){
cout << k << " ";
}
cout << endl;
for(auto k:b){
cout << k << " ";
}
cout << endl;
int input;
cin >> input;
return input;*/
return query(a.size(),b.size(),aa,bb);
}
int qcomp(vector<int> &a,vector<int> &b){
vector<int> temp1,temp2;
for(auto k:a){
for(auto j:comp[k]){
temp1.push_back(j);
}
}
for(auto k:b){
for(auto j:comp[k]){
temp2.push_back(j);
}
}
return q(temp1,temp2);
}
void road(int a,int b){
//cout << a << " " << b << "__" << endl;
setRoad(min(a,b),max(a,b));
}
void merge(int a,int b){
for(auto k:comp[color[b]]){
comp[color[a]].push_back(k);
}
int change = color[b];
for(int i=1;i<color.size();i++){
if(color[i]==change){
color[i] = color[a];
}
}
comp[change].clear();
}
void binarysearch(vector<int> left,vector<int> right){
vector<int> temp1;
vector<int> temp2;
for(auto k:left){
for(auto j:comp[k]){
temp1.push_back(j);
}
}
for(auto k:right){
for(auto j:comp[k]){
temp2.push_back(j);
}
}
left = temp1;
right = temp2;
while(left.size()!=1){
vector<int> curr;
for(int i=0;i<(left.size()+1)/2;i++){
curr.push_back(left[i]);
}
vector<int> curr2;
for(int i=(left.size()+1)/2;i<left.size();i++){
curr2.push_back(left[i]);
}
if(q(curr,right)==1){
left = curr;
}
else{
left = curr2;
}
}
swap(left,right);
while(left.size()!=1){
vector<int> curr;
for(int i=0;i<(left.size()+1)/2;i++){
curr.push_back(left[i]);
}
vector<int> curr2;
for(int i=(left.size()+1)/2;i<left.size();i++){
curr2.push_back(left[i]);
}
if(q(curr,right)==1){
left = curr;
}
else{
left = curr2;
}
}
assert(left.size()==1&&right.size()==1);
road(left[0],right[0]);
merge(left[0],right[0]);
}
int rec(vector<int> a){
vector<int> left,right;
for(int i=0;i<(a.size()+1)/2;i++){
left.push_back(a[i]);
}
for(int i=(a.size()+1)/2;i<a.size();i++){
right.push_back(a[i]);
}
if(left.size()==0||right.size()==0){
return 0;
}
if(qcomp(left,right)==0){
if(rec(left)==1){
return 1;
}
else{
if(rec(right)==1){
return 1;
}
}
}
else{
binarysearch(left,right);
return 1;
}
return 0;
}
void run(int n){
for(int i=0;i<color.size();i++){
comp[i].clear();
comp[i].push_back(i);
color[i] = i;
}
vector<int> current;
vector<int> alr;
for(int i=1;i<=n-1;i++){
//cout << "YES" << endl;
for(int j=1;j<=n;j++){
if(comp[j].size()!=0){
current.push_back(j);
}
}
rec(current);
current.clear();
}
}