Submission #896828

#	Time	Username	Problem	Language	Result	Execution time	Memory
896828		NeroZein	Meetings (JOI19_meetings)	C++17	100 / 100	576 ms	1248 KiB

meetings

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

using namespace std; 

int crt;

bool cmp(int i, int j) {
  //cout << "crt: " << crt << ' ' << i << ' ' << j << endl;
  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()];
  //cout << "O: " << root << ' ' << v << endl;
  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);
        //cout << "U: " << u << endl;
      } else {
        newvec[q].push_back(u);
      }
    }
  }
  //cout << endl; 
  sort(onpath.begin() + 1, onpath.end(), cmp);
  //cout << "ONPATH: ";
  //for (int i : onpath) cout << i << ' ';
  //cout << endl; 
  for (int i = 1; i < (int) onpath.size(); ++i) {
    int x = onpath[i - 1], y = onpath[i];
    if (x > y) swap(x, y);
    //cout << x << ' ' << y << endl; 
    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