Submission #312721

#	Time	Username	Problem	Language	Result	Execution time	Memory
312721		mohamedsobhi777	ICC (CEOI16_icc)	C++14	0 / 100	358 ms	1016 KiB

icc

#include<bits/stdc++.h>
#include "icc.h"

#define I inline void 
#define S struct 
#define vi vector<int> 
#define vii vector<pair<int,int>>
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std ; 
using ll = long long ; 
using ld = long double ; 

const int N = 1e5 + 7 , mod = 1e9 + 7 ; 
const int inf = N ; 
// How interesting!

int n ; 
int fat[N] ;
vector<pair<int,int> > ed ; 
int U , V ; 

inline int find(int x){return fat[x] = (x == fat[x] ? x : find(fat[x])) ; }

void link(int u , int v){
        u = find(u) ; 
        v = find(v) ;
        if(u!=v) 
                fat[u] = v; 
}
/*
bool ok(int u , int v){
        if( u == U && v == V)
                return 1 ; 
        if(u == V && v == U)
                return 1; 
        return 0 ; 
}

void setRoad(int u , int v){

        if(ok(u , v)){
                cout<<"ok " << u <<" " << v <<"\n" ;
                link(u , v) ; 
        }
        else{
                cout<< u <<" "<< v <<">>" ; 
                cout<<"bad" ;
                exit(0) ; 
        }
}

int query(int x , int y , vector<int> v1 , vector<int> v2){
        set<int> st ; 
        for(auto u : v1)
                st.insert(find(u)) ; 
        for(auto u : v2){
                if(st.find(find(u)) != st.end())
                        return 1 ; 
        }
        int m1 = 0 , m2 = 0 ;
        for(auto u : v1)
                if(u == U || u == V)
                        m1 = 1; 
        for(auto u : v2)
                if(u == U || u == V)
                        m2 = 1 ;
        if( m1 == 1 && m2 == 1 ){
                return 1 ; 
        }
        return 0 ; 
}

*/
int query1(int x , int y , vector<int> v1 , vector<int> v2){
        //return query(x , y , v1 , v2) ; 
        int *v11;
        int *v22 ; 
        v11 = new int[x] ; 
        v22 = new int [y] ; 
        for(int i = 0 ;i < x ; ++ i)
                v11[i] = v1[i] ; 
        for(int i = 0 ;i < y ; ++ i)
                v22[i] = v2[i] ; 
       return query(x , y , v11 , v22) ; 
}

void divide(vector<vector<int> > &vec){
        vector<vector<int> > ret ; 
        int sz = (int) vec.size() ; 
        for(int i = 0 ;i < sz ; ++ i){
                int sz2 = (int) vec[i].size() ; 
                //if(sz2 < 2)continue ; 
                vector<int> lhs, rhs ;
                for(int j = 0 ;j < sz2 ;++ j){
                        if(j < sz2 / 2 )
                                lhs.push_back(vec[i][j]) ; 
                        else 
                                rhs.push_back(vec[i][j]) ; 
                }
                if(lhs.size())
                ret.push_back(lhs) ; 
                if(rhs.size())
                ret.push_back(rhs) ; 
        }
        vec = ret ; 
}

vector<int> chd(int x){
        vector<int> ret ;
        for(int i = 1 ;i <= n; ++ i){
                if(find(i) == x)
                        ret.push_back(i) ;
        }
        return ret ;
}

int conquer(vector<vector<int> > &vec, int lmt = 1000000){
        int ret = 0 ; 
        vector<int> lhs, rhs ; 
        for(int i = 0 ; i < min(lmt , (int) vec.size() ) ; ++ i){
                for(auto u : vec[i]){
                        if(i&1)
                                for(auto v : chd(u))
                                        rhs.push_back(v) ; 
                        else for(auto v : chd(u))
                                lhs.push_back(v) ; 
                }
        }  
        return query1(lhs.size() , rhs.size() , lhs , rhs ) ; 
}

void print(vector<vector<int> > &vec){
        for(auto u : vec){
                for(auto v : u )
                        cout<< v <<" " ; 
                cout<<"\n" ; 
        } 
        cout<<"----------\n" ; 
}

vector<int> qur(vector<int> ve){
        vector<int> ret ; 
        for(auto u : ve)
                for(auto v : chd(u))
                        ret.push_back(v) ; 
        return ret; 
}

void divide_or_conquer(vector<int> hs){
        int sz = (int) hs.size() ; 
        /*int a = 0 , b = 0 ; 
        for(int i = 0 ;i < sz ;++ i){
                for(int j = i + 1; j < sz ; ++ j){
                        vector<int> q1 = qur({hs[i]}) , q2 = qur({hs[j]});
                        if(query1(q1.size() , q2.size() , q1 ,q2) ){
                                a = hs[i] ;
                                b = hs[j] ; 
                                i = j = sz ; 
                        }
                }
        }*/
        vector<vector<int> > dac { hs } ; 

        divide(dac) ; 
        
        int k = 0 ; 
        while(!conquer(dac)){
                divide(dac) ; 
        }       
        int A = 0 , B = 0 ; 
        sz = dac.size() ; 
        for(int i = 0 ;i + 1< sz ;++ i){
                vector<int> q1 = qur(dac[i]) , q2 = qur(dac[i+1]);
                if(query1(q1.size() , q2.size() , q1 ,q2) ){
                        A = i , B = i + 1; 
                        break ;
                        /*for(auto u1 : dac[i]){
                                for(auto u2 : dac[i+1]){
                                        vector<int> q11 = qur({u1}) , q22 = qur({u2});
                                        if(query1(q11.size() , q22.size() , q11 ,q22) ){
                                                a = u1 ;
                                                b = u2 ; 
                                        }
                                }
                        }*/
                }
                
        }
        assert(B) ; 
        /*int lo = 1, hi = (int) dac.size() ; 
        int lst = (int) dac.size() ; 
        while(lo<=hi){
                int mid = (lo+hi) >> 1;
                if(conquer(dac, mid)){
                        lst = mid ; 
                        hi = mid - 1; 
                }else lo = mid + 1; 
        }
        vector<int> qlhs = dac[lst-2] ,qrhs = dac[lst-1] ; */
        vector<int> qlhs = dac[A] ,qrhs = dac[B] ; 

        int llhs = 0 , rrhs = 0 ; 
        vector<int> q = qur(qlhs) ; 
        while(qlhs.size() && query1(qlhs.size() , qrhs.size() , qlhs , qrhs )){
                llhs = qlhs.back() ; 
                qlhs.pop_back() ; 
                q = qur(qlhs) ; 
        }
        if(llhs)qlhs.push_back(llhs) ; 
        q = qur(qrhs) ; 
        while(qrhs.size() && query1(qlhs.size() , qrhs.size() , qlhs , qrhs )){
                rrhs = qrhs.back() ; 
                qrhs.pop_back() ; 
                q = qur(qrhs) ; 
        }
        if(rrhs)qrhs.push_back(rrhs) ; 

        
        int a = qlhs.back() , b = qrhs.back() ; 

        for(int i = 1;i <= n; ++ i){
                for(int j = 1;j <= n ;++ j){
                        if(find(i) == a && find(j) == b && query1(1 ,1 , {i} , {j})){
                                setRoad(i , j) ; 
                                link(i , j) ;
                                return ; 
                        }
                }
        }

}

void run(int x){
        n = x;
        for(int i = 1;i <= n; ++ i)
                fat[i] = i ;
        /*bad_solve(n) ; 
        return ;*/ 
        for(int r = 0 ; r < n - 1; ++ r){
                //U = ed[r].first ; 
                //V = ed[r].second ; 

                vector<int> v ; 
                for(int i = 1;i <= n; ++ i){
                        if(i == fat[i])
                                v.push_back(i) ; 
                }
                divide_or_conquer(v) ; 
        }
}

Compilation message (stderr)

icc.cpp: In function 'int conquer(std::vector<std::vector<int> >&, int)':
icc.cpp:120:13: warning: unused variable 'ret' [-Wunused-variable]
  120 |         int ret = 0 ;
      |             ^~~
icc.cpp: In function 'void divide_or_conquer(std::vector<int>)':
icc.cpp:168:13: warning: unused variable 'k' [-Wunused-variable]
  168 |         int k = 0 ;
      |             ^

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