Submission #1176218

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176218		avighna	Meetings (JOI19_meetings)	C++20	100 / 100	689 ms	1044 KiB

meetings

#include <bits/stdc++.h>

int Query(int u, int v, int w);
void Bridge(int u, int v);

void Solve(int n) {
  auto query = [&](int a, int b, int c) {
    if (a == b or a == c) {
      return a;
    }
    if (b == c) {
      return b;
    }
    return Query(a, b, c);
  };
  auto bridge = [&](int a, int b) { Bridge(std::min(a, b), std::max(a, b)); };

  std::random_device rd;
  std::mt19937 rng(rd());

  auto solve = [&](auto &&self, std::vector<int> v) {
    if (v.size() < 2) {
      return;
    }
    if (v.size() < 3) {
      bridge(v[0], v[1]);
      return;
    }
    std::uniform_int_distribution<int> dist(0, v.size() - 1);
    int a = dist(rng);
    int b = a;
    while (a == b) {
      b = dist(rng);
    }
    a = v[a], b = v[b];
    std::vector<int> path;
    std::map<int, std::vector<int>> subtree;
    subtree[a].push_back(a), subtree[b].push_back(b);
    for (int i = 0; i < v.size(); ++i) {
      if (v[i] == a or v[i] == b) {
        continue;
      }
      int q = query(a, v[i], b);
      subtree[q].push_back(v[i]);
      if (q == v[i]) {
        path.push_back(v[i]);
      }
    }
    std::sort(path.begin(), path.end(),
              [&](int i, int j) { return query(a, i, j) == i; });
    if (path.empty()) {
      bridge(a, b);
    } else {
      bridge(a, path[0]);
      for (int i = 1; i < path.size(); ++i) {
        bridge(path[i - 1], path[i]);
      }
      bridge(path.back(), b);
    }
    for (auto &[u, sub] : subtree) {
      self(self, sub);
    }
  };

  std::vector<int> v(n);
  std::iota(v.begin(), v.end(), 0);
  solve(solve, v);
}

• Subtask 1: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71