Submission #1150775

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150775		fryingduc	Meetings (JOI19_meetings)	C++20	0 / 100	56 ms	704 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;
bool mark[maxn], in[maxn];

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;
  while (!cand.empty()) {
    for (auto i:cand) {
      mark[i] = 0;
      in[i] = 1;
    }
    shuffle(cand.begin(), cand.end(), rng);
    vector<int> nxt;
    int x = cand[0];
    nxt.push_back(x);
    mark[x] = 1;
    for (int i = 1; i < (int)cand.size(); ++i) {
      if (cur_anc[cand[i]] and in[cur_anc[cand[i]]]) {
//        debug(root, cand[i], cur_anc[cand[i]]);
        mark[cand[i]] = 1;
        nxt.push_back(cand[i]);
        continue;
      }
      int p = Query(root, x, cand[i]);
      if (p == root) {
        continue;
      }
      nxt.push_back(cand[i]);
      mark[cand[i]] = 1;
      if (p == cand[i]) {
        cur_anc[x] = cand[i];
        x = cand[i];
      } else {
        cur_anc[cand[i]] = x;
      }
    }    
//    debug(root, x);
    Bridge(min(root, x), max(root, x));
    vector<int> new_cand;
    for (auto i:cand) {
      in[i] = 0;
      if (!mark[i]) {
        new_cand.push_back(i);
      }
    }
    cand.swap(new_cand);
    calc(x, root, nxt);
  }
}

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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71