Submission #1276290

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276290		nguyn	Meetings (JOI19_meetings)	C++20	100 / 100	663 ms	848 KiB

meetings

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

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>

const int N = 2005;

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

void cal(int root, vector<int> &cand) {
    for (int i = 0; i < (int)cand.size(); i++) {
        if (cand[i] == root) {
            cand.erase(cand.begin() + i);
            break;
        }
    }
    if (cand.empty()) return;
    shuffle(cand.begin(), cand.end(), rng);
    vector<pii> vec;
    vector<int> chain;
    int u = cand[0];
    chain.pb(u);
    for (int i = 1; i < cand.size(); i++) {
        int p = Query(root, u, cand[i]);
        if (p == cand[i]) {
            chain.pb(p);
        }
        else {
            vec.pb({p, cand[i]});
        }
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < (int)vec.size(); i++) {
        vector<int> nxt;
        int j = i;
        nxt.pb(vec[i].F);
        while(j < (int)vec.size() && vec[i].F == vec[j].F) {
            nxt.pb(vec[j].S);
            j++;
        }
        shuffle(nxt.begin(), nxt.end(), rng);
        cal(nxt[0], nxt);
        i = j - 1;
    }
    sort(chain.begin(), chain.end(), [&](const int &x, const int &y) {
        return Query(root, x, y) == x;
    });
    for (int i = 0; i < (int)chain.size(); i++) {
        int u = chain[i];
        int v = (i == 0 ? root : chain[i - 1]);
        if (u > v) swap(u, v);
        Bridge(u, v);
    }
}

void Solve(int n) {
    vector<int> cand(n);
    iota(cand.begin(), cand.end(), 0);
    shuffle(cand.begin(), cand.end(), rng);
    cal(cand[0], cand);
}

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