Submission #1150786

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150786		Sharky	Meetings (JOI19_meetings)	C++20	0 / 100	19 ms	516 KiB

meetings

#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;

mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int u, int v) {
    return uniform_int_distribution<int> (u, v) (rng);
}

int n;
vector<int> res[2001];

void recur(int rt, vector<int> v) {
    int x = v[rnd(0, v.size() - 1)];
    vector<int> e;
    for (int i = 0; i < v.size(); i++) {
        if (v[i] == x) continue;
        int y = Query(rt, x, v[i]);
        e.push_back(y);
        if (v[i] != y) res[y].push_back(v[i]);
    }
    e.push_back(rt); e.push_back(x);
    sort(e.begin(), e.end());
    e.erase(unique(e.begin(), e.end()), e.end());
    if (!e.empty()) {
        vector<int> path = {rt, x};
        for (int i = 0; i < e.size(); i++) {
            if (e[i] == rt || e[i] == x) continue;
            int l = 1, r = path.size() - 1;
            while (l < r) {
                int mid = (l + r) / 2;
                if (Query(rt, path[mid], e[i]) == e[i]) r = mid;
                else l = mid + 1;
            }
            path.insert(path.begin() + l, e[i]);
        }
        for (int i = 1; i < path.size(); i++) Bridge(path[i-1], path[i]);
    }
    vector<pair<int, vector<int>>> vt;
    for (int& node : e) {
        if (!res[node].empty()) vt.push_back({node, res[node]});
        res[node].clear();
    }
    for (int i = 0; i < vt.size(); i++) recur(vt[i].first, vt[i].second);
}

void Solve(int N) { 
    n = N;
    vector<int> p;
    for (int i = 1; i < N; i++) p.push_back(i);
    recur(0, p);
}

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