Submission #24103

#	Time	Username	Problem	Language	Result	Execution time	Memory
24103		jiaqiyang	Park (JOI17_park)	C++14	100 / 100	479 ms	1444 KiB

park

#include "park.h"
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>

static const int N = 1500 + 10;

static int query(int a, int b, int tag[]) {
  if (a > b) std::swap(a, b);
  return Ask(a, b, tag);
}

static int n;
static int tag[N];

static std::vector<int> adj[N];

static void link(int a, int b) {
  if (a > b) std::swap(a, b);
  Answer(a, b);
  adj[a].push_back(b);
  adj[b].push_back(a);
}

static bool flag[N], mark[N];

static std::vector<int> res;

static std::vector<int> bfs(int s) {
  std::vector<int> res;
  res.push_back(s);
  for (int i = 0; i < res.size(); ++i) {
    int a = res[i];
    mark[a] = false;
    for (int j = 0; j < adj[a].size(); ++j) if (mark[adj[a][j]]) res.push_back(adj[a][j]);
  }
  return res;
}

static void connect(int a, std::vector<int> &cur) {
  for (int i = 0; i < n; ++i) tag[i] = 0;
  for (int i = 0; i < cur.size(); ++i) tag[cur[i]] = 1;
  tag[a] = 1;
  if (!query(a, cur[0], tag)) return;
  int l = 0, r = cur.size();
  while (l < r) {
    int mid = (l + r) >> 1;
    for (int i = 0; i < n; ++i) tag[i] = 0;
    for (int i = 0; i <= mid; ++i) tag[cur[i]] = 1;
    tag[a] = 1;
    if (query(a, cur[0], tag)) r = mid; else l = mid + 1;
  }
  int b = cur[l];
  link(a, b);
  for (int i = 0; i < cur.size(); ++i) mark[cur[i]] = true;
  mark[b] = false;
  std::vector< std::vector<int> > pool;
  for (int i = 0; i < cur.size(); ++i) if (mark[cur[i]]) pool.push_back(bfs(cur[i]));
  for (int i = 0; i < pool.size(); ++i) connect(a, pool[i]);
}

static void solve(int a) {
  for (int r = n;; solve(r)) {
    for (int i = 0; i < n; ++i) tag[i] = flag[i];
    tag[a] = 1;
    if (query(0, a, tag)) break;
    for (int l = 1; l < r;) {
      int mid = (l + r) >> 1;
      for (int i = 0; i < n; ++i) tag[i] = (i <= mid || flag[i]);
      tag[a] = 1;
      if (query(0, a, tag)) r = mid; else l = mid + 1;
    }
  }
  memcpy(mark, flag, sizeof mark);
  flag[a] = true;
  std::vector<int> cur = bfs(0);
  connect(a, cur);
}

void Detect(int _t, int _n) {
  n = _n;
  memset(flag, 0, sizeof flag);
  flag[0] = true;
  for (int i = 1; i < n; ++i) if (!flag[i]) solve(i);
}

Compilation message (stderr)

park.cpp: In function 'std::vector<int> bfs(int)':
park.cpp:33:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < res.size(); ++i) {
                     ^
park.cpp:36:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[a].size(); ++j) if (mark[adj[a][j]]) res.push_back(adj[a][j]);
                       ^
park.cpp: In function 'void connect(int, std::vector<int>&)':
park.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < cur.size(); ++i) tag[cur[i]] = 1;
                     ^
park.cpp:56:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < cur.size(); ++i) mark[cur[i]] = true;
                     ^
park.cpp:59:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < cur.size(); ++i) if (mark[cur[i]]) pool.push_back(bfs(cur[i]));
                     ^
park.cpp:60:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < pool.size(); ++i) connect(a, pool[i]);
                     ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 27 / 27
• Subtask 4: 30 / 30
• Subtask 5: 23 / 23