Submission #233159

#	Time	Username	Problem	Language	Result	Execution time	Memory
233159		AlexPop28	Meetings (JOI19_meetings)	C++14	100 / 100	956 ms	912 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void Ans(int a, int b) {
  if (a > b) swap(a, b);
  Bridge(a, b);
}

void Solve(vector<int> v) {
  if ((int)v.size() <= 2) {
    Ans(v[0], v[1]);
    return;
  }

  shuffle(v.begin(), v.end(), rng);

  vector<int> path;
  map<int, vector<int>> subtree;
  int root = v[0];
  int aux = v[1];
  for (int i = 2; i < (int)v.size(); ++i) {
    int ans = Query(root, aux, v[i]);
    if (ans == v[i]) {
      path.emplace_back(v[i]);
    } else {
      subtree[ans].emplace_back(v[i]);
    }
  }

  sort(path.begin(), path.end(), [&](int a, int b) {
    return Query(root, a, b) == a;
  });

  if (!path.empty()) {
    Ans(root, path[0]);
    for (int i = 0; i + 1 < (int)path.size(); ++i) {
      Ans(path[i], path[i + 1]);
    }
    Ans(path.back(), aux);
  } else {
    Ans(root, aux);
  }

  for (auto p : subtree) {
    p.second.emplace_back(p.first);
    Solve(p.second);
  }
}

void Solve(int n) {
  vector<int> v(n);
  iota(v.begin(), v.end(), 0);
  Solve(v);
}

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