제출 #1150787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150787		Sharky	Meetings (JOI19_meetings)	C++20	100 / 100	933 ms	976 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(min(path[i-1], path[i]), max(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: 7 / 7
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 71 / 71