| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 607285 |
2022-07-26T14:26:44 Z |
DanerZein |
ICC (CEOI16_icc) |
C++14 |
|
110 ms |
848 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N=110;
int pa[MAX_N];
void init(int n){
for(int i=0;i<=n;i++) pa[i]=i;
}
int findset(int x){
if(pa[x]==x) return x;
return pa[x]=findset(pa[x]);
}
bool issameset(int i,int j){
return findset(i)==findset(j);
}
void unionset(int i,int j){
if(!issameset(i,j)){
int u=findset(i),v=findset(j);
pa[u]=v;
}
}
int c=0;
int myQuery(vector<int> y,vector<int> x){
int t=y.size();
int *qu1=new int[t];
for(int i=0;i<t;i++)
qu1[i]=y[i];
t=x.size();
int *qu2=new int[t];
for(int i=0;i<t;i++)
qu2[i]=x[i];
c++;
return query(y.size(),x.size(),qu1,qu2);
}
vector<int> firstHalf(vector<int> x){
vector<int> f;
for(int i=0;i<x.size()/2;i++) f.push_back(x[i]);
return f;
}
vector<int> secondHalf(vector<int> x){
vector<int> f;
for(int i=x.size()/2;i<x.size();i++) f.push_back(x[i]);
return f;
}
void divide(vector<int> y,vector<int> x){
if(x.size()==1 && y.size()==1){
//cout<<x[0]<<" "<<y[0]<<endl;
setRoad(x[0],y[0]);
unionset(x[0],y[0]);
return;
}
vector<int> y1=firstHalf(y),y2=secondHalf(y);
vector<int> x1=firstHalf(x),x2=secondHalf(x);
if(myQuery(x1,y1)) divide(x1,y1);
else if(myQuery(x1,y2)) divide(x1,y2);
else if(myQuery(x2,y1)) divide(x2,y1);
else divide(x2,y2);
}
int N;
vector<int> conjun(vector<int> x){
vector<int> con;
for(int i=0;i<x.size();i++){
for(int j=1;j<=N;j++){
if(issameset(x[i],j)) con.push_back(j);
}
}
return con;
}
void divCon(vector<int> y,vector<int> x){
vector<int> y1=firstHalf(y),y2=secondHalf(y);
vector<int> x1=firstHalf(x),x2=secondHalf(x);
if(x.size()==1 && y.size()==1){
divide(conjun(x),conjun(y));
return;
}
if(myQuery(conjun(x1),conjun(y1))) divCon(x1,y1);
else if(myQuery(conjun(x2),conjun(y1))) divCon(x2,y1);
else if(myQuery(conjun(x1),conjun(y2))) divCon(x1,y2);
else divCon(x2,y2);
}
void findUnion(vector<int> con){
int k=log2(con.size());
for(int i=0;i<k;i++){
vector<int> c1,c2;
for(int j=0;j<con.size();j++){
if(j&(1<<i)) c1.push_back(con[j]);
else c2.push_back(con[j]);
}
if(myQuery(conjun(c1),conjun(c2))){
divCon(c1,c2);
return;
}
}
}
void run(int n){
N=n;
init(n);
for(int k=0;k<n-1;k++){
vector<int> con;
for(int i=1;i<=n;i++) con.push_back(findset(i));
sort(con.begin(),con.end());
con.erase(unique(con.begin(),con.end()),con.end());
findUnion(con);
}
}
Compilation message
icc.cpp: In function 'std::vector<int> firstHalf(std::vector<int>)':
icc.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<x.size()/2;i++) f.push_back(x[i]);
| ~^~~~~~~~~~~
icc.cpp: In function 'std::vector<int> secondHalf(std::vector<int>)':
icc.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | for(int i=x.size()/2;i<x.size();i++) f.push_back(x[i]);
| ~^~~~~~~~~
icc.cpp: In function 'std::vector<int> conjun(std::vector<int>)':
icc.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i=0;i<x.size();i++){
| ~^~~~~~~~~
icc.cpp: In function 'void findUnion(std::vector<int>)':
icc.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for(int j=0;j<con.size();j++){
| ~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
468 KB |
Ok! 230 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 223 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
548 KB |
Ok! 1240 queries used. |
| 2 |
Incorrect |
16 ms |
468 KB |
Not all edges were guessed! |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
110 ms |
800 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
632 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
62 ms |
720 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
60 ms |
848 KB |
Not all edges were guessed! |
| 2 |
Halted |
0 ms |
0 KB |
- |
