Submission #966294

#	Time	Username	Problem	Language	Result	Execution time	Memory
966294		kilkuwu	ICC (CEOI16_icc)	C++17	0 / 100	2 ms	604 KiB

icc

#ifndef LOCAL
#include "icc.h"
#else 
int query(int size_a, int size_b, int a[], int b[]);
void setRoad(int a, int b);
#endif

#include <bits/stdc++.h>

constexpr int mxN = 105;
int aa[mxN], bb[mxN];
int in_comp[mxN];
std::vector<int> comps[mxN];
int comps_size;

#ifdef LOCAL
#include "template/debug.hpp"
#else
#define dbg(...) ;
#define timer(...) ;
#endif

int my_query(std::vector<int> a, std::vector<int> b) {
  dbg(a, b);
  for (int i = 0; i < (int) a.size(); i++) aa[i] = a[i] + 1;
  for (int i = 0; i < (int) b.size(); i++) bb[i] = b[i] + 1;
  return query(a.size(), b.size(), aa, bb);
}

void merge_comp(int i, int j) {
  if (comps[i].size() < comps[j].size()) {
    std::swap(i, j);
  }
  comps[i].insert(comps[i].end(), comps[j].begin(), comps[j].end());
  for (int u : comps[j]) {
    in_comp[u] = i;
  }
  comps_size--;
  std::swap(comps[j], comps[comps_size]);
  for (int u : comps[j]) {
    in_comp[u] = j;
  }
}

std::array<std::vector<int>, 2> split_pool(int b) {
  std::vector<int> n1, n2;
  for (int i = 0; i < comps_size; i++) {
    if (i >> b & 1) {
      n1.insert(n1.end(), comps[i].begin(), comps[i].end());
    } else {
      n2.insert(n2.end(), comps[i].begin(), comps[i].end());
    }
  }
  return {n1, n2};
}

bool check_bit(int b) {
  auto [n1, n2] = split_pool(b);
  return my_query(n1, n2);
}

void deduce_one(std::vector<int>& left, std::vector<int>& right) {
  dbg(left, right);
  int lb = 0, rb = left.size() - 1;
  while (lb < rb) {
    int m = (lb + rb) / 2;
    // check from l -> m
    std::vector<int> to_ask;
    for (int i = lb; i <= m; i++) {
      to_ask.emplace_back(left[i]);
    }
    bool ok = my_query(to_ask, right);
    if (ok) {
      rb = m;
    } else {
      lb = m + 1;
    }
  }
  left = {left[rb]};
}

void run(int N) {
  comps_size = N;
  for (int i = 0; i < N; i++) {
    comps[i].emplace_back(i);
    in_comp[i] = i;
  }
  for (int tt = 0; tt + 1 < N; tt++) {
    dbg(tt, comps_size);
    for (int i = 0; i < comps_size; i++) {
      dbg(i, comps[i]);
    }
    int lg = std::__lg(comps_size - 1) + 1;
    for (int b = 0; b < lg; b++) {
      if (!check_bit(b)) continue;
      auto [l, r] = split_pool(b);

      deduce_one(l, r);
      deduce_one(r, l);

      dbg(l[0], r[0]);
      setRoad(l[0] + 1, r[0] + 1);
      merge_comp(in_comp[l[1]], in_comp[r[0]]);
      break;
    }
  }
}

#ifdef LOCAL
int N;
std::pair<int, int> roads[mxN];
std::vector<int> adj[mxN];
int id = 0;

void add_edge(int x) {
  auto [l, r] = roads[x];
  adj[l].push_back(r);
  adj[r].push_back(l);
}

int query(int size_a, int size_b, int a[], int b[]) {
  std::set<int> ab;
  for (int i = 0; i < size_b; i++) {
    ab.insert(b[i]);
  }
  for (int i = 0; i < size_a; i++) {
    for (int v : adj[a[i]]) {
      if (ab.count(v)) return 1;
    }
  }
  return 0;
}

void setRoad(int a, int b) {
  auto [l, r] = roads[id];
  id++;
  if (id + 1 < N) {
    add_edge(id);
  }

  if (l > r) std::swap(l, r);
  if (a > b) std::swap(a, b);
  assert(a == l && b == r);
}

int main() {
  std::cin >> N;
  for (int i = 0; i + 1 < N; i++) {
    std::cin >> roads[i].first >> roads[i].second;
  }
  add_edge(0);
  run(N);
}
#endif

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