Submission #896830

#	Time	Username	Problem	Language	Result	Execution time	Memory
896830		NeroZein	Meetings (JOI19_meetings)	C++17	100 / 100	577 ms	1236 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std; 

int crt;

bool cmp(int i, int j) {
  return (Query(crt, i, j) == i);
}

void rec(int root, vector<int>& vec) {
  if (vec.empty()) return; 
  crt = root;
  map<int, vector<int>> newvec; 
  int v = vec[rand() % vec.size()];
  vector<int> onpath = {root, v};
  for (int u : vec) {
    if (u != v) {
      int q = Query(root, v, u);
      if (q == u) {
        onpath.push_back(u);
      } else {
        newvec[q].push_back(u);
      }
    }
  }
  sort(onpath.begin() + 1, onpath.end(), cmp);
  for (int i = 1; i < (int) onpath.size(); ++i) {
    int x = onpath[i - 1], y = onpath[i];
    if (x > y) swap(x, y);
    Bridge(x, y);
  }
  for (int u : onpath) {
    rec(u, newvec[u]); 
  }
}

void Solve(int N) {
  int root = rand() % N;
  vector<int> vec;
  for (int i = 0; i < N; ++i) {
    if (i != root) {
      vec.push_back(i);
    }
  }
  rec(root, vec); 
}

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