Submission #1172971

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172971		patgra	Meetings (JOI19_meetings)	C++20	100 / 100	701 ms	1048 KiB

meetings

#include <bits/stdc++.h>

#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))

constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl

#define ll long long
#define pb push_back

using namespace std;

#include "meetings.h"

mt19937 rnd(2137);

void myBridge(int v, int u) {
    DC << "  @@@  Bridge " << v << ' ' << u << eol;
    if(u > v) swap(u, v);
    Bridge(u, v);
}

void sortPath(int S, int E, vector<int> V) {
    DC << " Sorting path: " << S << " ( ";
    repIn(i, V) DC << i << ' ';
    DC << ") " << E << eol;
    if(V.empty()) {
        myBridge(S, E);
        return;
    }
    auto mid = V[rnd() % V.size()];
    vector<int> L, R;
    repIn(i, V) if(i != mid) (Query(S, i, mid) == i ? L : R).pb(i);
    sortPath(S, mid, L);
    sortPath(mid, E, R);
}

void DQ(vector<int> V) {
    DC << "DQ: ";
    repIn(i, V) DC << i << ' ';
    DC << eol;
    if(V.size() == 2) myBridge(V[0], V[1]);
    if(V.size() <= 2) return;
    int S = rnd() % V.size(), E = rnd() % (V.size() - 1);
    if(E >= S) E++;
    S = V[S], E = V[E];
    unordered_map<int, vector<int>> subtree;
    vector<int> path;
    subtree[S].pb(S);
    subtree[E].pb(E);
    repIn(i, V) if(i != S && i != E) {
        auto qa = Query(S, E, i);
        if(qa == i) path.pb(i);
        subtree[qa].pb(i);
    }
    sortPath(S, E, path);
    repIn2(pathGuy, st, subtree) DQ(st);
}

void Solve(int N) {
    vector<int> V;
    rep(i, 0, N) V.pb(i);
    DQ(V);
}

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