| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 966756 |
2024-04-20T09:57:42 Z |
berr |
ICC (CEOI16_icc) |
C++17 |
|
110 ms |
1256 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
vector<int> vis(101);
/*vector<array<int, 2>> edge;
int newa, newb;
**/
struct dsu{
vector<int> p, s;
int c, n;
vector<vector<int>> val;
dsu(int _n){
n=_n; c=n;
val.resize(n+1);
p.resize(n+1); s.resize(n+1);
fill(s.begin(), s.end(), 1);
iota(p.begin(), p.end(), 0);
for(int i=1; i<=n; i++){
val[i].push_back(i);
}
}
int find(int x){
if(p[x]==x) return x;
return p[x] = find(p[x]);
}
void merge(int x, int y){
x=find(x); y=find(y);
if(s[x] > s[y]) swap(x, y);
p[x] = y;
for(auto i: val[x]){
val[y].push_back(i);
}
s[x]+=s[y];
}
};
dsu d(105);
/*
int query(int a, int b, int x[], int y[]){
for(int i=0; i<a; i++){
for(int l=0; l<b; l++){
for(auto [c, d]: edge){
if(x[i]==c && y[l]==d) return 1;
if(x[i]==d && y[l]==c) return 1;
}
}
}
return 0;
}
void setRoad(int a, int b){
if(!(a==newa && b==newb) && !(a==newb && b==newa)){
cout<<a<<" "<<b<<"bruh";
}
else{
cout<<a<<" "<<b<<"tadaa";
cout<<"\n";
}
};*/
int que(vector<vector<int>> aa, vector<vector<int>> bb){
vector<int> a, b;
for(auto i: aa) for(auto l: i) a.push_back(l);
for(auto i: bb) for(auto l: i) b.push_back(l);
int x[a.size()], y[b.size()];
int siz_a = a.size(), siz_b=b.size();
for(int i=0; i<siz_a; i++){
x[i] = a[i];
}
for(int i=0; i<siz_b; i++){
y[i] = b[i];
}
return query(siz_a, siz_b, x, y);
}
int que2(vector<int> a, vector<int> b){
int x[a.size()], y[b.size()];
int siz_a = a.size(), siz_b=b.size();
for(int i=0; i<siz_a; i++){
x[i] = a[i];
}
for(int i=0; i<siz_b; i++){
y[i] = b[i];
}
return query(siz_a, siz_b, x, y);
}
void coz2(vector<int> a, vector<int> b){
while(a.size()>1){
vector<int> pf;
for(int i=0; i<a.size()/2; i++){
pf.push_back(a[i]);
}
if(que2(pf, b)){
a= pf;
}
else{
pf.clear();
for(int i=a.size()/2; i<a.size(); i++){
pf.push_back(a[i]);
}
a=pf;
}
}
while(b.size()>1){
vector<int> pf;
for(int i=0; i<b.size()/2; i++){
pf.push_back(b[i]);
}
if(que2(a, pf)){
b= pf;
}
else{
pf.clear();
for(int i=b.size()/2; i<b.size(); i++){
pf.push_back(b[i]);
}
b=pf;
}
}
vis[a[0]]=1; vis[b[0]]=1;
d.merge(a[0], b[0]);
setRoad(a[0], b[0]);
}
void coz(vector<vector<int>> a, vector<vector<int>> b){
while(a.size()>1){
vector<vector<int>> pf;
for(int i=0; i<a.size()/2; i++){
pf.push_back(a[i]);
}
if(que(pf, b)){
a= pf;
}
else{
pf.clear();
for(int i=a.size()/2; i<a.size(); i++){
pf.push_back(a[i]);
}
a=pf;
}
}
while(b.size()>1){
vector<vector<int>> pf;
for(int i=0; i<b.size()/2; i++){
pf.push_back(b[i]);
}
if(que(a, pf)){
b= pf;
}
else{
pf.clear();
for(int i=b.size()/2; i<b.size(); i++){
pf.push_back(b[i]);
}
b=pf;
}
}
coz2(a[0], b[0]);
}
void run(int n){
for(int i=0; i<=n; i++) vis[i]=0;
for(int i=0; i<n-1; i++){
/* cin >> newa >> newb;
edge.push_back({newa, newb});
*/
vector<int> visp(n+1);
vector<vector<int>> a, b, x;
for(int l=1; l<=n; l++){
if(visp[d.find(l)]) continue;
x.push_back(d.val[d.find(l)]);
visp[d.find(l)] = 1;
}
vector<vector<vector<int>>> aa;
vector<vector<vector<int>>> bb;
aa.push_back(x);
while(1){
vector<vector<vector<int>>> new_aa;
vector<vector<vector<int>>> new_bb;
int sa=0, sb=0;
for(auto i: aa){
vector<vector<int>> ay, by;
for(int l=0; l<i.size(); l++){
if(l<i.size()/2){
ay.push_back(i[l]);
sa++;
}
else if(l==i.size()/2 && i.size()%2){
if(sa+1 <= sb+i.size()/2){
ay.push_back(i[l]);
sa++;
}
else{
by.push_back(i[l]);
sb++;
}
}
else{
by.push_back(i[l]);
sb++;
}
}
if(ay.size()==0||by.size()==0) continue;
else{
new_aa.push_back(ay);
new_bb.push_back(by);
}
}
for(auto i: bb){
vector<vector<int>> ay, by;
for(int l=0; l<i.size(); l++){
if(l<i.size()/2){
ay.push_back(i[l]);
sa++;
}
else if(l==i.size()/2 && i.size()%2){
if(sa+1 <= sb+i.size()/2){
ay.push_back(i[l]);
sa++;
}
else{
by.push_back(i[l]);
sb++;
}
}
else{
by.push_back(i[l]);
sb++;
}
}
if(ay.size()==0||by.size()==0) continue;
else{
new_aa.push_back(ay);
new_bb.push_back(by);
}
}
vector<vector<int>> ca, cb;
for(auto i: new_aa)
for(auto l: i) ca.push_back(l);
for(auto i: new_bb)
for(auto l: i)
cb.push_back(l);
if(que(ca, cb)){
int s=-1;
auto check=[&](int val){
vector<vector<int>> pf, fp;
for(int i=0; i<=val; i++){
for(auto l: new_aa[i]){
pf.push_back(l);
}
for(auto l: new_bb[i]){
fp.push_back(l);
}
}
if(que(pf, fp)) return 1;
return 0;
};
for(int j=6; j>=0; j--){
int tmp = s+(1<<j);
if(tmp <new_aa.size()-1){
if(check(tmp)) continue;
s = tmp;
}
}
a=new_aa[s+1]; b=new_bb[s+1];
break;
}
else{
aa=new_aa; bb=new_bb;
}
}
coz(a, b);
}
}
/*
int main(){
int n; cin >> n;
run(n);
cout<<"tamam";
}*/
Compilation message
icc.cpp: In function 'void coz2(std::vector<int>, std::vector<int>)':
icc.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
110 | for(int i=0; i<a.size()/2; i++){
| ~^~~~~~~~~~~
icc.cpp:119:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=a.size()/2; i<a.size(); i++){
| ~^~~~~~~~~
icc.cpp:129:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int i=0; i<b.size()/2; i++){
| ~^~~~~~~~~~~
icc.cpp:138:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | for(int i=b.size()/2; i<b.size(); i++){
| ~^~~~~~~~~
icc.cpp: In function 'void coz(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
icc.cpp:156:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
156 | for(int i=0; i<a.size()/2; i++){
| ~^~~~~~~~~~~
icc.cpp:165:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for(int i=a.size()/2; i<a.size(); i++){
| ~^~~~~~~~~
icc.cpp:175:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
175 | for(int i=0; i<b.size()/2; i++){
| ~^~~~~~~~~~~
icc.cpp:184:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for(int i=b.size()/2; i<b.size(); i++){
| ~^~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:229:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
229 | for(int l=0; l<i.size(); l++){
| ~^~~~~~~~~
icc.cpp:230:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
230 | if(l<i.size()/2){
| ~^~~~~~~~~~~
icc.cpp:234:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
234 | else if(l==i.size()/2 && i.size()%2){
| ~^~~~~~~~~~~~
icc.cpp:235:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
235 | if(sa+1 <= sb+i.size()/2){
| ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:261:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
261 | for(int l=0; l<i.size(); l++){
| ~^~~~~~~~~
icc.cpp:262:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
262 | if(l<i.size()/2){
| ~^~~~~~~~~~~
icc.cpp:266:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
266 | else if(l==i.size()/2 && i.size()%2){
| ~^~~~~~~~~~~~
icc.cpp:267:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
267 | if(sa+1 <= sb+i.size()/2){
| ~~~~~^~~~~~~~~~~~~~~~
icc.cpp:319:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::vector<int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
319 | if(tmp <new_aa.size()-1){
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
600 KB |
Ok! 110 queries used. |
| 2 |
Correct |
7 ms |
604 KB |
Ok! 110 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
600 KB |
Ok! 624 queries used. |
| 2 |
Correct |
23 ms |
728 KB |
Ok! 500 queries used. |
| 3 |
Correct |
25 ms |
604 KB |
Ok! 537 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
85 ms |
604 KB |
Ok! 1560 queries used. |
| 2 |
Correct |
71 ms |
612 KB |
Ok! 1165 queries used. |
| 3 |
Correct |
84 ms |
604 KB |
Ok! 1501 queries used. |
| 4 |
Correct |
82 ms |
776 KB |
Ok! 1510 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
760 KB |
Ok! 1461 queries used. |
| 2 |
Correct |
86 ms |
1024 KB |
Ok! 1467 queries used. |
| 3 |
Correct |
87 ms |
768 KB |
Ok! 1380 queries used. |
| 4 |
Correct |
85 ms |
752 KB |
Ok! 1523 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
600 KB |
Ok! 1419 queries used. |
| 2 |
Correct |
80 ms |
600 KB |
Ok! 1388 queries used. |
| 3 |
Correct |
80 ms |
756 KB |
Ok! 1378 queries used. |
| 4 |
Correct |
83 ms |
748 KB |
Ok! 1437 queries used. |
| 5 |
Correct |
94 ms |
1256 KB |
Ok! 1552 queries used. |
| 6 |
Correct |
110 ms |
760 KB |
Ok! 1511 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
79 ms |
600 KB |
Ok! 1357 queries used. |
| 2 |
Correct |
83 ms |
760 KB |
Ok! 1486 queries used. |
