제출 #1150759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150759		fryingduc	Meetings (JOI19_meetings)	C++20	0 / 100	36 ms	696 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];

int lab[maxn];
int find(int u) {
  return lab[u] < 0 ? u : lab[u] = find(lab[u]);
}

void join(int u, int v) {
  u = find(u), v = find(v);
  if (u == v) return;
  if (lab[u] > lab[v]) swap(u, v);
  lab[u] += lab[v];
  lab[v] = u;
}

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]);
      if (p == cand[i]) {
        x = cand[i];
      }
    }    
//    debug(root, x);
    Bridge(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: 0 / 7
• Subtask 2: 0 / 10
• Subtask 3: 0 / 12
• Subtask 4: 0 / 71