| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605175 |
2022-07-25T13:39:38 Z |
pere_gil |
ICC (CEOI16_icc) |
C++14 |
|
390 ms |
476 KB |
#include "bits/stdc++.h"
#include "icc.h"
using namespace std;
const int MAX_N=105;
vector<int> p(MAX_N);
void init(int n){
iota(p.begin(),p.end(),0);
}
int find_set(int n){
return (p[n]==n) ? n : p[n]=find_set(p[n]);
}
bool same_set(int a, int b){
return find_set(a)==find_set(b);
}
void union_set(int a, int b){
if(same_set(a,b)) return;
p[find_set(b)]=find_set(a);
}
vector<int> get_set(int n, int a){
vector<int> res;
for(int i=0;i<n;i++) if(same_set(i,a)) res.push_back(i);
return res;
}
bool make_query(vector<int> &a, vector<int> &b){
int A[a.size()],B[b.size()];
for(int i=0;i<a.size();i++) A[i]=a[i]+1;
for(int i=0;i<b.size();i++) B[i]=b[i]+1;
return query(a.size(),b.size(),A,B);
}
bool make_query(int a, int b){
int A[1]={a+1},B[1]={b+1};
return query(1,1,A,B);
}
void pri(vector<int> v){
for(int i=0;i<v.size();i++) printf("%d ",v[i]+1); printf("\n");
}
void run(int n){
init(n);
for(int edge=1;edge<n;edge++){
//printf("in edge %d\n",edge);
bool found=false;
for(int i=0;i<n;i++){
if(find_set(i)!=i) continue;
if(found) break;
for(int j=i+1;j<n;j++){
if(find_set(j)!=j || found) continue;
vector<int> a=get_set(n,i),b=get_set(n,j);
if(!make_query(a,b)) continue;
//printf("is between set %d and %d\n",i+1,j+1);
//printf("%d: ",i+1); pri(a);
//printf("%d: ",j+1); pri(b);
for(int i=0;i<a.size();i++){
if(found) continue;
for(int j=0;j<b.size();j++){
if(found) continue;
if(make_query(a[i],b[j])){
//printf("found %d ; %d\n",a[i]+1,b[j]+1);
setRoad(a[i]+1,b[j]+1);
union_set(a[i],b[j]);
found=true;
}
}
}
}
}
//printf("\n");
}
}
Compilation message
icc.cpp: In function 'bool make_query(std::vector<int>&, std::vector<int>&)':
icc.cpp:29:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for(int i=0;i<a.size();i++) A[i]=a[i]+1;
| ~^~~~~~~~~
icc.cpp:30:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | for(int i=0;i<b.size();i++) B[i]=b[i]+1;
| ~^~~~~~~~~
icc.cpp: In function 'void pri(std::vector<int>)':
icc.cpp:39:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i=0;i<v.size();i++) printf("%d ",v[i]+1); printf("\n");
| ~^~~~~~~~~
icc.cpp:39:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
39 | for(int i=0;i<v.size();i++) printf("%d ",v[i]+1); printf("\n");
| ^~~
icc.cpp:39:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
39 | for(int i=0;i<v.size();i++) printf("%d ",v[i]+1); printf("\n");
| ^~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i=0;i<a.size();i++){
| ~^~~~~~~~~
icc.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int j=0;j<b.size();j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
472 KB |
Ok! 665 queries used. |
| 2 |
Correct |
38 ms |
468 KB |
Ok! 659 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
472 KB |
Number of queries more than 5000 out of 2500 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
390 ms |
472 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
345 ms |
476 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 |
468 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
286 ms |
472 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
