Submission #383056

#	Time	Username	Problem	Language	Result	Execution time	Memory
383056		PurpleCrayon	Meetings (JOI19_meetings)	C++17	100 / 100	1331 ms	1172 KiB

meetings

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

//helper functions
#define sz(v) int(v.size())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l, int r){
	return uniform_int_distribution<int>(l, r)(rng);
}
int qry(int a, int b, int c) {
    // cerr << "qry: " << a << ' ' << b << ' ' << c << endl;
    assert(a != b && b != c && a != c);
    return Query(a, b, c);
}
void upd(int a, int b) {
    if (a >= b) swap(a, b);
    // cerr << "upd: " << a << ' ' << b << endl;
    Bridge(a, b);
}
//end helper functions

int n;

void rec(int root, vector<int> cand) {
    if (sz(cand) == 0) return;
    if (sz(cand) == 1) {
        upd(root, cand[0]);
        return;
    }
    int m = sz(cand);
    int end = cand[rnd(0, m-1)];

    // cerr << "root, end: " << root << ' ' << end << endl;
    vector<int> repr(m), path;
    for (int i = 0; i < m; i++) {
        repr[i] = cand[i] == end ? end : qry(root, end, cand[i]);
        if (repr[i] == cand[i] && cand[i] != end) { //on path
            path.push_back(cand[i]);
        }
    }
    sort(path.begin(), path.end(), [&](int a, int b){
        return qry(root, a, b) == a;
    });

    path.insert(path.begin(), root);
    path.push_back(end);
    // cerr << "path: "; for (auto v : path) cerr << v << ' '; cerr << endl;

    for (int i = 1; i < sz(path); i++)
        upd(path[i-1], path[i]);

    map<int, int> loc;
    for (int i = 0; i < sz(path); i++) loc[path[i]] = i;
    vector<vector<int>> nxt(sz(path));
    for (int i = 0; i < m; i++) {
        if (repr[i] != cand[i]) {
            nxt[loc[repr[i]]].push_back(cand[i]);
        }
    }
    for (int i = 0; i < sz(nxt); i++) {
        rec(path[i], nxt[i]);
    }
}
void Solve(int _n) {
    n = _n;

    vector<int> al(n); iota(al.begin(), al.end(), 0);
    int root = rnd(0, n-1);
    // cerr << root << endl;

    al.erase(find(al.begin(), al.end(), root));
    rec(root, al);
}

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