Submission #1060282

#	Time	Username	Problem	Language	Result	Execution time	Memory
1060282		MilosMilutinovic	Park (JOI17_park)	C++14	100 / 100	261 ms	852 KiB

park

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

using namespace std;

static int Place[1400];

void Detect(int T, int n) {
  vector<bool> done(n);
  done[0] = true;
  vector<vector<int>> g(n);
  function<void(int)> Solve = [&](int v) {
    if (done[v]) {
      return;
    }
    while (true) {
      for (int i = 0; i < n; i++) {
        Place[i] = done[i] ? 1 : 0;
      }
      Place[v] = 1;
      if (Ask(0, v, Place)) {
        break;
      }
      int low = 0, high = n - 1, p = -1;
      while (low <= high) {
        int mid = (low + high) >> 1;
        for (int i = 0; i < n; i++) {
          if (done[i] || i == v || i <= mid) {
            Place[i] = 1;
          } else {
            Place[i] = 0;
          }
        }
        if (Ask(0, v, Place)) {
          p = mid;
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      Solve(p);
    }
    vector<int> que(1, 0);
    for (int b = 0; b < (int) que.size(); b++) {
      int i = que[b];
      for (int j : g[i]) {
        que.push_back(j);
      }
    }
    vector<int> ver;
    vector<int> a(1, 0);
    vector<bool> was(n);
    for (int i = 0; i < (int) a.size(); i++) {
      int root = a[i];
      vector<int> f;
      function<void(int)> Dfs = [&](int v) {
        if (was[v]) {
          return;
        }
        f.push_back(v);
        for (int u : g[v]) {
          Dfs(u);
        }
      };
      while (true) {
        f.clear();
        Dfs(root);
        if (was[root]) {
          break;
        }
        for (int i = 0; i < n; i++) {
          Place[i] = 0;
        }
        for (int i : f) {
          Place[i] = 1;
        }
        Place[v] = 1;
        if (!Ask(min(root, v), max(root, v), Place)) {
          break;
        }
        int low = 0, high = (int) f.size() - 1, p = -1;
        while (low <= high) {
          int mid = low + high >> 1;
          for (int i = 0; i < n; i++) {
            Place[i] = 0;
          }
          for (int i = 0; i <= mid; i++) {
            Place[f[i]] = 1;
          }
          Place[v] = 1;
          if (Ask(min(root, v), max(root, v), Place)) {
            p = f[mid];
            high = mid - 1;
          } else {
            low = mid + 1;
          }
        }
        was[p] = true;
        ver.push_back(p);
        for (int u : g[p]) {
          a.push_back(u);
        }
      }
    }
    int p = ver[0];
    g[p].push_back(v);
    for (int u : ver) {
      Answer(min(u, v), max(u, v));
    }
    done[v] = true;
  };
  for (int i = 1; i < n; i++) {
    if (!done[i]) {
      Solve(i);
    }
  }
}

Compilation message (stderr)

park.cpp: In lambda function:
park.cpp:83:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~

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