Submission #940425

#	Time	Username	Problem	Language	Result	Execution time	Memory
940425		parlimoos	ICC (CEOI16_icc)	C++14	0 / 100	2 ms	860 KiB

icc

//Be Name KHODA
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include "icc.h"
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define pp pop_back
#define lb lower_bound
#define ub upper_bound
#define cl clear
#define bg begin
#define arr(x) array<int , x>
#define endl '\n'

int n;
int dsu[101];
vector<int> cs;
vector<arr(2)> sgs[10];
vector<int> dsuset[101];

void init(){
    fill(&dsu[0] , &dsu[n + 1] , -1);
    for(int i = 1 ; i <= n ; i++) cs.pb(i) , dsuset[i].pb(i);
}
int findDsu(int v){
    if(dsu[v] == -1) return v;
    return (dsu[v] = findDsu(dsu[v]));
}
void uDsu(int a , int b){
    a = findDsu(a) , b = findDsu(b);
    if((int)dsuset[a].size() < (int)dsuset[b].size()) swap(a , b);
    dsu[b] = a , cs.erase((lb(cs.bg() , cs.end() , b)));
    for(int v : dsuset[b]) dsuset[a].pb(v);
}
int getSet(){
    int sz[2];
    for(int i = 0 ; i < 10 ; i++){
        sz[0] = 0 , sz[1] = 0;
        for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
            for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
                sz[(sg & 1)] += (int)dsuset[cs[v]].size();
            }
        }
        int a[sz[0]] , b[sz[1]];
        int cnt1 = 0 , cnt2 = 0;
        for(int sg = 0 ; sg < (int)sgs[i].size() ; sg++){
            for(int v = sgs[i][sg][0] ; v <= sgs[i][sg][1] ; v++){
                for(int u : dsuset[cs[v]]){
                    if((sg & 1)) b[cnt2++] = u;
                    else a[cnt1++] = u;
                }
            }
        }
        int d = query(sz[0] , sz[1] , a , b);
        if(d == 1) return i;
    }
    // cout << "Ay Kheda!\n";
}
arr(2) f(){
    for(int i = 0 ; i < 10 ; i++) sgs[i].cl();
    int c = (((int)cs.size() - 1) >> 1);
    sgs[0].pb({0 , c}) , sgs[0].pb({c + 1 , (int)cs.size() - 1});
    for(int i = 0 ; i < 10 ; i++){
        for(auto sg : sgs[i]){
            if(sg[0] == sg[1]) sgs[i + 1].pb({sg[0] , sg[1]});
            else{
                c = (sg[0] + sg[1] - 1) >> 1;
                sgs[i + 1].pb({sg[0] , c}) , sgs[i + 1].pb({c + 1 , sg[1]});
            }
        }
    }
    int inx = getSet();
    vector<int> a , b;
    for(int sg = 0 ; sg < (int)sgs[inx].size() ; sg++){
        for(int v = sgs[inx][sg][0] ; v <= sgs[inx][sg][1] ; v++){
            for(int u : dsuset[cs[v]]){
                if((sg & 1)) b.pb(u);
                else a.pb(u);
            }
        }
    }
    int l = 0 , r = (int)a.size() - 1;
    while(r > l){
        int c = (l + r - 1) >> 1;
        int sz[2] = {c - l + 1 , (int)b.size()};
        int aa[sz[0]] , bb[sz[1]];
        for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[i];
        for(int i = 0 ; i < sz[0] ; i++) aa[i] = a[l + i];
        int d = query(sz[0] , sz[1] , aa , bb);
        if(d == 1) r = c;
        else l = c + 1;
    }
    int ans1 = l;
    l = 0 , r = (int)b.size() - 1;
    while(r > l){
        int c = (l + r - 1) >> 1;
        int sz[2] = {1 , c - l + 1};
        int aa[sz[0]] , bb[sz[1]];
        for(int i = 0 ; i < sz[1] ; i++) bb[i] = b[l + i];
        aa[0] = a[ans1];
        int d = query(sz[0] , sz[1] , aa , bb);
        if(d == 1) r = c;
        else l = c + 1;
    }
    return {a[ans1] , b[l]};
}
void run(int N){
    n = N;
    init();
    for(int i = 1 ; i < n ; i++){
        arr(2) d = f();
        setRoad(d[0] , d[1]);
        uDsu(d[0] , d[1]);
    }
}

Compilation message (stderr)

icc.cpp: In function 'int getSet()':
icc.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
   61 | }
      | ^

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