Submission #1150762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150762		fryingduc	Meetings (JOI19_meetings)	C++20	29 / 100	439 ms	860 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];

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

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: 0 / 71