Submission #1307142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307142		KickingKun	Meetings (JOI19_meetings)	C++20	100 / 100	976 ms	864 KiB

meetings

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

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int random(int l, int r) {
  return uniform_int_distribution <int> (l, r)(rng);
}

vector <pair <int, int>> res;

void dnc(const vector <int> &node) {
  if (node.size() == 1) return;
  if (node.size() == 2) {
    res.emplace_back(node[0], node[1]);
    // cerr << "Path " << node[0] << ' ' << node[1] << endl;
    return;
  }

  int l = random(0, node.size() - 2), r = random(l + 1, node.size() - 1);
  int u = node[l], v = node[r];

  // cerr << "Path " << u << ' ' << v << endl;

  vector <int> path, ask(node.size());
  for (int i = 0; i < node.size(); i++) if (i != l && i != r) {
    int w = node[i]; ask[i] = Query(u, v, w);
    if (ask[i] != u && ask[i] != v) path.emplace_back(ask[i]);
  }

  sort (path.begin(), path.end());
  path.resize(unique(path.begin(), path.end()) - path.begin());

  sort (path.begin(), path.end(), [&] (int x, int y) {
    return Query(u, x, y) == x;
  });
  path.emplace_back(v);

  for (int i = 0; i < path.size(); i++) {
    if (i == 0) res.emplace_back(u, path[i]);
    else res.emplace_back(path[i - 1], path[i]);
  }

  path.emplace_back(u); sort (path.begin(), path.end());
  vector <vector <int>> group(path.size() + 1);

  for (int i = 0; i < node.size(); i++) {
    if (i == l) ask[i] = u;
    if (i == r) ask[i] = v;
    int id = lower_bound(path.begin(), path.end(), ask[i]) - path.begin();
    group[id].emplace_back(node[i]);
  }

  for (int i = 0; i < path.size(); i++)
    dnc(group[i]);
}

void Solve(int n) {
  vector <int> init(n);
  iota(init.begin(), init.end(), 0);
  res.clear(); dnc(init);

  for (auto &[u, v]: res) {
    if (u > v) swap(u, v);
    Bridge(u, v);
  }
}

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