Submission #1150791

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150791		fryingduc	Meetings (JOI19_meetings)	C++20	100 / 100	834 ms	936 KiB

meetings

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

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)    
#endif

const int maxn = 2005;
vector<int> g[maxn];
int cur_anc[maxn];
int n;

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

void calc(int root, int prev, vector<int> &cand) {
  for (int i = 0; i < (int)cand.size(); ++i) {
    if (cand[i] == root) {
      cand.erase(cand.begin() + i);
      break;
    }
  }
//  debug(root, cand);
  if (cand.empty()) return;
  shuffle(cand.begin(), cand.end(), rng);
  vector<pair<int, int>> subtree;
  vector<int> chain;
  int x = cand[0];
  for (int i = 1; i < (int)cand.size(); ++i) {
    int p = Query(root, x, cand[i]);
    if (p == cand[i]) {
      chain.push_back(p);
    } else {
      subtree.emplace_back(p, cand[i]);
    }
  }
  sort(subtree.begin(), subtree.end());
  for (int i = 0; i < (int)subtree.size(); ++i) {
    vector<int> niu;
    int cur = 0;
    while (i + cur < (int)subtree.size() and subtree[i].first == subtree[i + cur].first) {
      niu.push_back(subtree[i + cur].second);
      ++cur;
    }
    niu.push_back(subtree[i].first);
    shuffle(niu.begin(), niu.end(), rng);
    calc(niu[0], root, niu);
    i = i + cur - 1;
  }
  sort(chain.begin(), chain.end());
  chain.erase(unique(chain.begin(), chain.end()), chain.end());
  sort(chain.begin(), chain.end(), [&](const int &x, const int &y) -> bool {
    return Query(root, x, y) == x;
  });
  chain.push_back(x);
  for (int i = 0; i < (int)chain.size(); ++i) {
    int u = chain[i], v = (i == 0 ? root : chain[i - 1]);
    if (u > v) swap(u, v);
    Bridge(u, v);
  }
}

void Solve(int N) {
  n = N;
  vector<int> cand;
  for (int i = 0; i < n; ++i) {
    cand.push_back(i);
  }
  calc(0, -1, cand);
}

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