제출 #1306905

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306905		KickingKun	Meetings (JOI19_meetings)	C++20	0 / 100	676 ms	106284 KiB

meetings

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

const int MAXN = 300;
int save[MAXN][MAXN][MAXN];

int get(int a, int b, int c) {
  if (a > b) swap(a, b);
  if (a > c) swap(a, c);
  if (b > c) swap(b, c);

  if (save[a][b][c] != -1) return save[a][b][c];
  return save[a][b][c] = Query(a, b, c);
}

void Solve(int n) {
  memset(save, -1, sizeof save);

  int root = 0;
  vector <tuple <int, int, bool>> edges;

  for (int v = 1; v < n; v++) {
    bool isEdge = true;
    for (int w = 1; w < n && isEdge; w++) if (v != w) {
      if (get(root, w, v) == w) isEdge = false;
    }
    if (isEdge) edges.emplace_back(root, v, false);
  }

  while (edges.size() < n - 1) {
    for (auto &[u, v, end]: edges) if (end == false) {
      vector <int> candidates;
      for (int w = 0; w < n; w++) if (u != w && v != w) {
        if (get(u, v, w) == v) {
          bool updated = false;
          for (int &pre: candidates) if (get(u, w, pre) == w) {
            pre = w; updated = true;
          }
          if (!updated) candidates.emplace_back(w);
        }
      }

      if (candidates.empty()) end = true;
      else {
        sort (candidates.begin(), candidates.end());
        candidates.resize(unique(candidates.begin(), candidates.end()) - candidates.begin());
        for (int nxt: candidates) edges.emplace_back(v, nxt, false);
        break;
      }
    }
  }

  for (auto &[u, v, end]: edges) {
    if (u > v) swap(u, v);
    Bridge(u, v);
    // cerr << u << ' ' << v << endl;
  }
}

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