| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 101237 |
2019-03-18T03:26:51 Z |
ShaneOng |
ICC (CEOI16_icc) |
C++14 |
|
437 ms |
724 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
int n;
typedef pair<int,int> ii;
vector<int> p,rnk,adj[109];
int findS(int a){
return a==p[a]?a:(p[a]=findS(p[a]));
}
void unionS(int a,int b){
if(findS(a)!=findS(b)){
int i=findS(a),j=findS(b);
if(rnk[i]<rnk[j])
p[i]=j;
else{
p[j]=i;
if(rnk[i]==rnk[j])
rnk[i]++;
}
}
}
vector<int> conv(vector<int> a){
vector<int> newa;
unordered_set<int> us;
for(int x:a){
us.insert(x);
}
for(int x=0;x<n;x++)
if(us.find(findS(x))!=us.end())
newa.push_back(x+1);
return newa;
}
ii stuff(vector<int> a,vector<int> b){
int qu=0;
if((int)a.size()>0&&(int)b.size()>0){
vector<int> tempa=conv(a),tempb=conv(b);
qu=query(tempa.size(),tempb.size(),&tempa[0],&tempb[0]);
}
/*printf("\na:");
for(int x:a)
printf("%d ",x);
printf("\n");
printf("b:");
for(int x:b)
printf("%d ",x);
printf("\n");*/
int na=(int)a.size(),nb=(int)b.size();
ii res=ii(-1,-1);
if(qu==0){
vector<int> aa,ab,ba,bb;
if(na>1){
for(int x=0;x<na;x++){
if(x<na/2)
aa.push_back(a[x]);
else
ab.push_back(a[x]);
}
res=max(res,stuff(aa,ab));
}
if(nb>1){
for(int x=0;x<nb;x++){
if(x<nb/2)
ba.push_back(b[x]);
else
bb.push_back(b[x]);
}
res=max(res,stuff(ba,bb));
}
return res;
}else{
a=conv(a),b=conv(b);
while((int)a.size()>1){
vector<int> a1,a2;
for(int x=0;x<(int)a.size();x++){
if(x<(int)a.size()/2)
a1.push_back(a[x]);
else
a2.push_back(a[x]);
}
int qu=query(a1.size(),b.size(),&a1[0],&b[0]);
if(qu==0){
a=a2;
}else
a=a1;
}
while((int)b.size()>1){
vector<int> b1,b2;
for(int x=0;x<(int)b.size();x++){
if(x<(int)b.size()/2)
b1.push_back(b[x]);
else
b2.push_back(b[x]);
}
int qu=query(a.size(),b1.size(),&a[0],&b1[0]);
if(qu==0){
b=b2;
}else
b=b1;
}
//printf("%d %d\n",a[0],b[0]);
return ii(a[0],b[0]);
}
}
void run(int nn) {
n=nn;
for(int x=0;x<n;x++){
p.push_back(x);
rnk.push_back(0);
}
for(int x=0;x<n-1;x++){
int ctr=0;
vector<int> arr[2];
for(int y=0;y<n;y++){
if(findS(y)==y){
arr[ctr].push_back(y);
ctr=1-ctr;
}
}
ii ans=stuff(arr[0],arr[1]);
adj[ans.first-1].push_back(ans.second-1);
adj[ans.second-1].push_back(ans.first-1);
unionS(ans.second-1,ans.first-1);
//printf("%d %d\n",ans.first,ans.second);
setRoad(ans.first,ans.second);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
512 KB |
Ok! 96 queries used. |
| 2 |
Correct |
9 ms |
512 KB |
Ok! 105 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
632 KB |
Ok! 751 queries used. |
| 2 |
Correct |
109 ms |
572 KB |
Ok! 1403 queries used. |
| 3 |
Correct |
115 ms |
512 KB |
Ok! 1390 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
437 ms |
724 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
364 ms |
560 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
310 ms |
632 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
278 ms |
568 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
