| # | Time | Username | Problem | Language | Result | Execution time | Memory | 
|---|---|---|---|---|---|---|---|
| 1014065 | thangdz2k7 | Meetings (JOI19_meetings) | C++17 | 0 ms | 0 KiB | 
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd
long long Rand(long long l, long long h) {
    assert(l <= h);
    return l + rd() * 1LL * rd() % (h - l + 1);
}
void cen(vector <int> &cur){
    int n = cur.size(); if (n == 1) return;
    int root = cur[Rand(0, n - 1)];
    vector <vector <int>> sub;
    int sz = 0;
    for (auto u : cur){
        if (u == root) continue;
        bool used = false;
        for (int i = 0; i < sz; ++ i){
            int par = sub[i][0];
            int lca = Query(root, par, u);
            if (lca == root) continue;
            sub[i].push_back(u);
            if (lca == u) swap(sub[i][sub[i].size() - 1], sub[i][0]);
            used = true;
        }
        if (!used) {
            sub.push_back({u});
            ++ sz;
        }
    }
    for (int i = 0; i < sub.size(); ++ i){
        Bridge(root, sub[i][0]);
        cen(sub[i]);
    }
}
void solve(int N){
    vector <int> cur = {};
    for (int i = 0; i < N; ++ i) cur.push_back(i);
    cen(cur);
}
