제출 #1246667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246667		The_Samurai	Meetings (JOI19_meetings)	C++20	29 / 100	1111 ms	1232 KiB

meetings

#include "meetings.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
using namespace std;

mt19937 rng(231241);

void Solve(int n) {
    auto rec = [&](auto &rec, vector<int> vec) -> void {
        // for (int x: vec) cout << x << ' ';
        // cout << endl;
        if (vec.size() == 1) return;
        if (vec.size() == 2) {
            Bridge(min(vec[0], vec[1]), max(vec[0], vec[1]));
            return;
        }
        shuffle(vec.begin(), vec.end(), rng);
        int root = vec[0];
        vector<vector<int>> sub(1);
        sub[0].emplace_back(vec[1]);
        for (int i = 2; i < vec.size(); i++) {
            shuffle(sub.begin(), sub.end(), rng);
            bool found = false;
            for (int j = 0; j < sub.size(); j++) {
                int x = Query(root, sub[j][0], vec[i]);
                // cout << root << ' ' << sub[j][0] << ' ' << vec[i] << ' ' << x << endl;
                if (x == root) continue;

                sub[j].emplace_back(vec[i]);
                if (x == vec[i]) swap(sub[j][0], sub[j].back());
                found = true;
                break;
            }
            if (!found) sub.emplace_back(vector<int>{vec[i]});
        }
        // cout << root << " -> ";
        // for (int i = 0; i < sub.size(); i++) cout << sub[i][0] << ' ';
        // cout << endl;
        for (int i = 0; i < sub.size(); i++) Bridge(min(root, sub[i][0]), max(root, sub[i][0]));
        for (int i = 0; i < sub.size(); i++) rec(rec, sub[i]);
    };
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    rec(rec, ord);
}

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