Submission #218309

#	Time	Username	Problem	Language	Result	Execution time	Memory
218309		rama_pang	Meetings (JOI19_meetings)	C++14	100 / 100	878 ms	992 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

void SolvePath(int root, int endpoint, vector<int> &path) { // sorting algorithm to solve path subproblem
  stable_sort(begin(path), end(path), [&](int l, int r) {
    if (l == root) return true;
    if (l == endpoint) return false;
    if (r == root) return false;
    if (r == endpoint) return true;
    return Query(root, l, r) == l; // l is the nearer one to root
  });

  for (int i = 1; i < (int) path.size(); i++) {
    Bridge(min(path[i - 1], path[i]), max(path[i - 1], path[i]));
  }
}

void SolveTree(int root, vector<int> &nodes) {
  if (nodes.empty()) return;

  shuffle(begin(nodes), end(nodes), rnd);
  int endpoint = nodes.back();
  nodes.pop_back();

  map<int, vector<int>> S;
  vector<int> path = {root, endpoint};

  for (auto &v : nodes) {
    int q = Query(root, endpoint, v);
    if (v == q) {
      path.emplace_back(v);
    } else {
      S[q].emplace_back(v);
    }
  }

  nodes.clear();
  nodes.shrink_to_fit();

  SolvePath(root, endpoint, path);

  for (auto &v : path) {
    SolveTree(v, S[v]);
  }
}

void Solve(int N) {
  int root = rnd() % N;
  vector<int> nodes;

  for (int i = 0; i < N; i++) {
    if (i == root) continue;
    nodes.emplace_back(i);
  }

  return SolveTree(root, nodes);
}

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