Submission #1306909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306909		KickingKun	Meetings (JOI19_meetings)	C++20	0 / 100	687 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, calc]: edges) if (calc == false) {
      vector <int> candidates;
      for (int w = 0; w < n; w++) if (u != w && v != w) {
        if (get(u, v, w) == v) {
          bool bad = false;
          for (int i = 0; i < candidates.size() && !bad;) {
            int cur = get(v, w, candidates[i]);
            if (cur == w) {
              swap(candidates[i], candidates.back());
              candidates.pop_back();
            }
            else if (cur == candidates[i]) bad = true;
            else ++i;
          }
          if (!bad) candidates.emplace_back(w);
        }
      }

      if (candidates.empty()) calc = true;
      else {
        calc = true;
        for (int nxt: candidates) 
          edges.emplace_back(v, nxt, false);
        break;
      }
    }
  }

  for (auto &[u, v, calc]: 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