oj.uz

Submission #1060282

# Submission time Handle Problem Language Result Execution time Memory
1060282 2024-08-15T12:38:30 Z MilosMilutinovic Park (JOI17_park) C++14
100 / 100
 261 ms 852 KB 
#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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 7 ms 480 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 11 ms 348 KB Output is correct
5 Correct 17 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 684 KB Output is correct
2 Correct 106 ms 600 KB Output is correct
3 Correct 138 ms 600 KB Output is correct
4 Correct 249 ms 604 KB Output is correct
5 Correct 259 ms 604 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 564 KB Output is correct
2 Correct 118 ms 344 KB Output is correct
3 Correct 139 ms 560 KB Output is correct
4 Correct 103 ms 348 KB Output is correct
5 Correct 159 ms 592 KB Output is correct
6 Correct 142 ms 592 KB Output is correct
7 Correct 109 ms 816 KB Output is correct
8 Correct 141 ms 828 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 344 KB Output is correct
2 Correct 146 ms 592 KB Output is correct
3 Correct 152 ms 592 KB Output is correct
4 Correct 168 ms 592 KB Output is correct
5 Correct 203 ms 592 KB Output is correct
6 Correct 195 ms 596 KB Output is correct
7 Correct 195 ms 580 KB Output is correct
8 Correct 182 ms 596 KB Output is correct
9 Correct 175 ms 816 KB Output is correct
10 Correct 190 ms 576 KB Output is correct
11 Correct 202 ms 592 KB Output is correct
12 Correct 165 ms 596 KB Output is correct
13 Correct 205 ms 600 KB Output is correct
14 Correct 184 ms 592 KB Output is correct
15 Correct 255 ms 592 KB Output is correct
16 Correct 111 ms 344 KB Output is correct
17 Correct 261 ms 852 KB Output is correct
18 Correct 184 ms 848 KB Output is correct
19 Correct 243 ms 592 KB Output is correct
20 Correct 173 ms 828 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 596 KB Output is correct
2 Correct 144 ms 600 KB Output is correct
3 Correct 128 ms 596 KB Output is correct
4 Correct 207 ms 596 KB Output is correct
5 Correct 133 ms 564 KB Output is correct
6 Correct 237 ms 624 KB Output is correct
7 Correct 224 ms 596 KB Output is correct
8 Correct 227 ms 596 KB Output is correct
9 Correct 200 ms 596 KB Output is correct
10 Correct 157 ms 588 KB Output is correct
11 Correct 202 ms 580 KB Output is correct
12 Correct 175 ms 580 KB Output is correct
13 Correct 185 ms 596 KB Output is correct
14 Correct 153 ms 576 KB Output is correct
15 Correct 204 ms 596 KB Output is correct
16 Correct 120 ms 596 KB Output is correct
17 Correct 257 ms 604 KB Output is correct
18 Correct 189 ms 584 KB Output is correct