Submission #966833

#TimeUsernameProblemLanguageResultExecution timeMemory
966833berrICC (CEOI16_icc)C++17
100 / 100
98 ms860 KiB
#include <bits/stdc++.h> #include "icc.h" using namespace std; vector<int> vis(101); 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 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); } 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); return que2(a, b); } void coz(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); while(a.size()>1){ vector<int> pf, pf2; for(int i=0; i<a.size(); i++){ if(i<a.size()/2) pf.push_back(a[i]); else pf2.push_back(a[i]); } if(que2(pf, b)) a= pf; else a=pf2; } while(b.size()>1){ vector<int> pf, pf2; for(int i=0; i<b.size(); i++){ if(i<b.size()/2) pf.push_back(b[i]); else pf2.push_back(b[i]); } if(que2(a, pf)) b= pf; else b=pf2; } vis[a[0]]=1; vis[b[0]]=1; d.merge(a[0], b[0]); setRoad(a[0], b[0]); } void run(int n){ for(int i=0; i<n-1; i++){ 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, bb; aa.push_back(x); while(1){ vector<vector<vector<int>>> new_aa, 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]); else by.push_back(i[l]); } 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]); else by.push_back(i[l]); } 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); } return que(pf, fp); }; for(int j=6; j>=0; j--){ int tmp = s+(1<<j); if(tmp <new_aa.size()-1 && !check(tmp)) s=tmp; } a=new_aa[s+1]; b=new_bb[s+1]; break; } else aa=new_aa; bb=new_bb; } coz(a, b); } }

Compilation message (stderr)

icc.cpp: In function 'void coz(std::vector<std::vector<int> >, std::vector<std::vector<int> >)':
icc.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for(int i=0; i<a.size(); i++){
      |                      ~^~~~~~~~~
icc.cpp:71:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             if(i<a.size()/2) pf.push_back(a[i]);
      |                ~^~~~~~~~~~~
icc.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for(int i=0; i<b.size(); i++){
      |                      ~^~~~~~~~~
icc.cpp:81:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |             if(i<b.size()/2) pf.push_back(b[i]);
      |                ~^~~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:113:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 for(int l=0; l<i.size(); l++){
      |                              ~^~~~~~~~~
icc.cpp:114:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                     if(l<i.size()/2) ay.push_back(i[l]);
      |                        ~^~~~~~~~~~~
icc.cpp:128:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |                 for(int l=0; l<i.size(); l++){
      |                              ~^~~~~~~~~
icc.cpp:129:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |                     if(l<i.size()/2) ay.push_back(i[l]);
      |                        ~^~~~~~~~~~~
icc.cpp:158: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]
  158 |                     if(tmp <new_aa.size()-1 && !check(tmp)) s=tmp;
      |                        ~~~~^~~~~~~~~~~~~~~~
icc.cpp:164:13: warning: this 'else' clause does not guard... [-Wmisleading-indentation]
  164 |             else aa=new_aa; bb=new_bb;
      |             ^~~~
icc.cpp:164:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'else'
  164 |             else aa=new_aa; bb=new_bb;
      |                             ^~
icc.cpp:109:17: warning: unused variable 'sa' [-Wunused-variable]
  109 |             int sa=0, sb=0;
      |                 ^~
icc.cpp:109:23: warning: unused variable 'sb' [-Wunused-variable]
  109 |             int sa=0, sb=0;
      |                       ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...