Submission #344325

#	Time	Username	Problem	Language	Result	Execution time	Memory
344325		milleniumEeee	Meetings (JOI19_meetings)	C++17	100 / 100	716 ms	1004 KiB

meetings

 #include "meetings.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
using namespace std;

const int MAXN = 2003; // дерево индексация с 0...n-1
vector <pair<int, int>> ans; // u < v
int n;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int get_rand() {
  int x = rng();
  if (x < 0) {
    x = -x;
  }
  return x;
};

int gen(int l, int r) {
  return l + get_rand() % (r - l + 1);
}

void print(int u, int v) {
  if (u > v) {
    swap(u, v);
  }
  Bridge(u, v);
}

void calc(vector<int> &graph) {
  int root = -1, son = -1;
  while (root == son) {
    root = graph[gen(0, szof(graph) - 1)];
    son = graph[gen(0, szof(graph) - 1)];
  }
  // a = root
  // b = child
  set <int> st;
  vector <int> bambook;
  map <int, vector<int>> sub;
  for (int vertex : graph) {
    if (vertex == root || vertex == son) {
      continue;
    }
    int lca = Query(root, son, vertex);      
    st.insert(lca);
    sub[lca].push_back(vertex);
  }
  st.erase(son);
  st.erase(root);
  for (int el : st) {
    bambook.push_back(el);
  }
  sort(all(bambook), [&](int A, int B) {
    int lca = Query(root, A, B);
    return (A == lca);
  });
  bambook.insert(bambook.begin(), root);
  bambook.push_back(son);
  for (int i = 0; i + 1 < szof(bambook); i++) {
    print(bambook[i], bambook[i + 1]);
  }
  sub[root].push_back(root);
  sub[son].push_back(son);
  for (auto el : sub) {
    if (szof(el.second) > 1) {
      calc(el.second);
    }
  }
}

void Solve(int nn) {
  n = nn;
  vector<int> graph;
  for (int i = 0; i < n; i++) {
    graph.push_back(i);
  }
  calc(graph);
}

/*
5
0 1
1 2
2 3
3 4
*/

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