Submission #1125685

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125685		OI_Account	Meetings (JOI19_meetings)	C++20	100 / 100	1022 ms	2008 KiB

meetings

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

const int N = 2000;

mt19937 rng(time(0));
int ucmp;

void write(int u, int v) {
    u--, v--;
    Bridge(min(u, v), max(u, v));
}

int get(int u, int v, int w) {
    return Query(u - 1, v - 1, w - 1) + 1;
}

void solveSmall(vector<int> vec) {
    if (vec.size() == 1)
        return;
    if (vec.size() == 2) {
        write(vec[0], vec[1]);
        return;
    }
    int x = get(vec[0], vec[1], vec[2]);
    for (auto y: vec)
        if (x != y)
            write(x, y);
}

bool cmp(int x, int y) {
    return get(ucmp, x, y) == x;
}

void checkPath(vector<int> path, int u, int v) {
    ucmp = u;
    sort(path.begin(), path.end(), cmp);
    for (int i = 1; i < path.size(); i++)
        write(path[i - 1], path[i]);
    if (path.size() == 0)
        write(u, v);
    else {
        write(u, path[0]);
        write(path.back(), v);
    }
}

void solve(vector<int> vec) {
    if (vec.size() <= 3) {
        solveSmall(vec);
        return;
    }
    shuffle(vec.begin(), vec.end(), rng);
    int u = vec[0], v = vec[1];
    vector<int> path, x[N + 10];
    for (int i = 2; i < vec.size(); i++) {
        int w = get(u, v, vec[i]);
        x[w].push_back(vec[i]);
        if (w == vec[i])
            path.push_back(w);
    }
    checkPath(path, u, v);
    x[u].push_back(u);
    x[v].push_back(v);
    for (auto u: vec)
        if (x[u].size())
            solve(x[u]);
}

void Solve(int N) {
    vector<int> vec;
    for (int i = 1; i <= N; i++)
        vec.push_back(i);
    solve(vec);
}

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