Submission #966756

#	Time	Username	Problem	Language	Result	Execution time	Memory
966756		berr	ICC (CEOI16_icc)	C++17	100 / 100	110 ms	1256 KiB

icc

#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 (stderr)

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){
      |                        ~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10