oj.uz

Submission #282622

# Submission time Handle Problem Language Result Execution time Memory
282622 2020-08-24T16:06:03 Z rama_pang Park (JOI17_park) C++14
67 / 100
 550 ms 928 KB 
#include "park.h"
#include <bits/stdc++.h>
using namespace std;

void Detect(int T, int N) {
  vector<int> graph;
  vector<int> candidate;
  vector<pair<int, int>> edges;

  graph.emplace_back(0);
  for (int i = 1; i < N; i++) {
    candidate.emplace_back(i);
  }

  const auto CreateVector = [&](int l, int r, vector<int> a) {
    vector<int> res;
    for (int i = l; i <= r; i++) {
      res.emplace_back(a[i]);
    }
    return res;
  };

  const auto IsConnected = [&](int node, vector<int> g) -> bool {
    vector<int> query(N, 0);
    for (auto i : g) {
      query[i] = 1;
    }
    query[node] = 1;
    return Ask(min(g[0], node), max(g[0], node), query.data());
  };

  const auto IsConnectedTrough = [&](int node, vector<int> g, vector<int> add) -> bool {
    vector<int> query(N, 0);
    for (auto i : g) {
      query[i] = 1;
    }
    for (auto i : add) {
      query[i] = 1;
    }
    query[node] = 1;
    return Ask(min(g[0], node), max(g[0], node), query.data());
  };

  const auto Connect = [&](int node) -> void {
    vector<vector<int>> adj(N);
    for (auto e : edges) {
      adj[e.first].emplace_back(e.second);
      adj[e.second].emplace_back(e.first);
    }
    vector<int> vis;
    vector<int> invis(N, 0);
    vis.emplace_back(0);
    invis[0] = 1;
    for (int ptr = 0; ptr < (int) vis.size(); ptr++) {
      int u = vis[ptr];
      for (auto v : adj[u]) {
        if (!invis[v]) {
          invis[v] = 1;
          vis.emplace_back(v);
        }
      }
    }

    int lo = 0, hi = int(vis.size()) - 1;
    while (lo < hi) {
      int md = (lo + hi) / 2;
      if (IsConnected(node, CreateVector(0, md, vis))) {
        hi = md;
      } else {
        lo = md + 1;
      }
    }
    edges.emplace_back(node, vis[lo]);
  };

  while (!candidate.empty()) {
    int node = candidate.back();
    vector<int> path;
    function<void(int, int)> FindPath = [&](int l, int r) {
      vector<int> c;
      if (l == 0) {
        c = graph;
      } else {
        c = {l};
      }
      if (IsConnected(r, c)) {
        path.emplace_back(r);
      } else {
        // Find a node on path from l to r
        int lo = 0, hi = int(candidate.size()) - 1;
        while (lo < hi) {
          int md = (lo + hi) / 2;
          if (IsConnectedTrough(r, c, CreateVector(0, md, candidate))) {
            hi = md;
          } else {
            lo = md + 1;
          }
        }
        FindPath(l, candidate[lo]);
        FindPath(candidate[lo], r);
      }
    };

    FindPath(0, node);
    for (auto u : path) {
      Connect(u);
      graph.emplace_back(u);
      candidate.erase(find(begin(candidate), end(candidate), u));
    }
  }

  for (auto e : edges) {
    int u = e.first, v = e.second;
    if (u > v) {
      swap(u, v);
    }
    Answer(u, v);
  }
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 760 KB Output is correct
2 Correct 503 ms 888 KB Output is correct
3 Correct 497 ms 760 KB Output is correct
4 Correct 538 ms 632 KB Output is correct
5 Correct 546 ms 888 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 668 KB Output is correct
2 Correct 421 ms 512 KB Output is correct
3 Correct 440 ms 632 KB Output is correct
4 Correct 384 ms 680 KB Output is correct
5 Correct 452 ms 760 KB Output is correct
6 Correct 421 ms 512 KB Output is correct
7 Correct 399 ms 512 KB Output is correct
8 Correct 433 ms 632 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 221 ms 504 KB Output is correct
2 Correct 473 ms 512 KB Output is correct
3 Correct 448 ms 640 KB Output is correct
4 Correct 463 ms 512 KB Output is correct
5 Correct 412 ms 512 KB Output is correct
6 Correct 428 ms 632 KB Output is correct
7 Correct 434 ms 632 KB Output is correct
8 Correct 413 ms 760 KB Output is correct
9 Correct 414 ms 632 KB Output is correct
10 Correct 495 ms 632 KB Output is correct
11 Correct 467 ms 760 KB Output is correct
12 Correct 420 ms 632 KB Output is correct
13 Correct 429 ms 804 KB Output is correct
14 Correct 466 ms 888 KB Output is correct
15 Correct 427 ms 512 KB Output is correct
16 Correct 442 ms 928 KB Output is correct
17 Correct 536 ms 760 KB Output is correct
18 Correct 505 ms 700 KB Output is correct
19 Correct 455 ms 632 KB Output is correct
20 Correct 434 ms 612 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 442 ms 512 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -