oj.uz

Submission #24103

# Submission time Handle Problem Language Result Execution time Memory
24103 2017-05-31T00:46:36 Z jiaqiyang Park (JOI17_park) C++14
100 / 100
 479 ms 1444 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1308 KB Output is correct
2 Correct 9 ms 1308 KB Output is correct
3 Correct 6 ms 1308 KB Output is correct
4 Correct 26 ms 1308 KB Output is correct
5 Correct 69 ms 1440 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 1440 KB Output is correct
2 Correct 156 ms 1440 KB Output is correct
3 Correct 209 ms 1440 KB Output is correct
4 Correct 476 ms 1440 KB Output is correct
5 Correct 479 ms 1440 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 1444 KB Output is correct
2 Correct 336 ms 1440 KB Output is correct
3 Correct 309 ms 1440 KB Output is correct
4 Correct 246 ms 1440 KB Output is correct
5 Correct 356 ms 1440 KB Output is correct
6 Correct 309 ms 1440 KB Output is correct
7 Correct 289 ms 1440 KB Output is correct
8 Correct 316 ms 1444 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 1308 KB Output is correct
2 Correct 346 ms 1440 KB Output is correct
3 Correct 326 ms 1440 KB Output is correct
4 Correct 329 ms 1440 KB Output is correct
5 Correct 296 ms 1440 KB Output is correct
6 Correct 299 ms 1440 KB Output is correct
7 Correct 346 ms 1440 KB Output is correct
8 Correct 293 ms 1444 KB Output is correct
9 Correct 303 ms 1444 KB Output is correct
10 Correct 346 ms 1440 KB Output is correct
11 Correct 323 ms 1440 KB Output is correct
12 Correct 309 ms 1440 KB Output is correct
13 Correct 319 ms 1440 KB Output is correct
14 Correct 299 ms 1440 KB Output is correct
15 Correct 326 ms 1444 KB Output is correct
16 Correct 306 ms 1440 KB Output is correct
17 Correct 476 ms 1440 KB Output is correct
18 Correct 309 ms 1440 KB Output is correct
19 Correct 376 ms 1440 KB Output is correct
20 Correct 293 ms 1440 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 1440 KB Output is correct
2 Correct 396 ms 1440 KB Output is correct
3 Correct 359 ms 1440 KB Output is correct
4 Correct 319 ms 1440 KB Output is correct
5 Correct 436 ms 1444 KB Output is correct
6 Correct 419 ms 1440 KB Output is correct
7 Correct 369 ms 1440 KB Output is correct
8 Correct 313 ms 1440 KB Output is correct
9 Correct 333 ms 1440 KB Output is correct
10 Correct 323 ms 1444 KB Output is correct
11 Correct 303 ms 1440 KB Output is correct
12 Correct 319 ms 1440 KB Output is correct
13 Correct 283 ms 1440 KB Output is correct
14 Correct 416 ms 1440 KB Output is correct
15 Correct 303 ms 1440 KB Output is correct
16 Correct 319 ms 1440 KB Output is correct
17 Correct 466 ms 1440 KB Output is correct
18 Correct 273 ms 1440 KB Output is correct