Submission #1289811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289811		julia_08	ICC (CEOI16_icc)	C++20	100 / 100	72 ms	620 KiB

icc

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

using namespace std;

// void setRoad(int a, int b);
// int query(int sz_a, int sz_b, int a[], int b[]);

const int MAXN = 110;
const int LOG = 7;

int a[LOG][MAXN], b[LOG][MAXN];

int sz_a[LOG], sz_b[LOG];

int pai[MAXN], comp[MAXN];

int cur_A[MAXN], cur_B[MAXN];

int bit;

int get(int v){
  if(v == pai[v]) return v;
  return pai[v] = get(pai[v]);
}

void dsu_union(int a, int b){
  a = get(a); b = get(b);
  pai[a] = b;
}

bool check_A(int m){

  int cur_sz = m + 1;

  for(int i=0; i<cur_sz; i++) cur_A[i] = a[bit][i];
  for(int i=0; i<sz_b[bit]; i++) cur_B[i] = b[bit][i];

  return query(cur_sz, sz_b[bit], cur_A, cur_B);

}

int bs_A(){

  int l = 0, r = sz_a[bit];

  while(l < r){
    int m = l + (r - l) / 2;
    if(check_A(m)) r = m;
    else l = m + 1;
  }

  return r;

}


bool check_B(int m){

  int cur_sz = m + 1;

  for(int i=0; i<sz_a[bit]; i++) cur_A[i] = a[bit][i];
  for(int i=0; i<cur_sz; i++) cur_B[i] = b[bit][i];

  return query(sz_a[bit], cur_sz, cur_A, cur_B);

}

int bs_B(){

  int l = 0, r = sz_b[bit] - 1;

  while(l < r){
    int m = l + (r - l) / 2;
    if(check_B(m)) r = m;
    else l = m + 1;
  }

  return r;

}

void solve(int n){

  int cnt = 0;

  for(int i=1; i<=n; i++) if(i == get(i)) comp[i] = cnt++;

  int log = __lg(cnt) + 1;

  for(int i=0; i<log; i++){

    sz_a[i] = sz_b[i] = 0;

    for(int j=1; j<=n; j++){

      if(comp[get(j)] & (1 << i)){
        a[i][sz_a[i]++] = j;
      } else b[i][sz_b[i]++] = j;

    }

  }

  bit = -1;

  for(int i=0; i<log; i++){
    if(query(sz_a[i], sz_b[i], a[i], b[i])){
      bit = i;
      break;
    }
  }

  int pos_a = bs_A(), pos_b = bs_B();

  setRoad(a[bit][pos_a], b[bit][pos_b]);

  dsu_union(a[bit][pos_a], b[bit][pos_b]);

}

void run(int n){

  for(int i=1; i<=n; i++) pai[i] = i;

  for(int i=0; i<(n - 1); i++) solve(n);

}

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