Submission #230100

#	Time	Username	Problem	Language	Result	Execution time	Memory
230100		PeppaPig	Meetings (JOI19_meetings)	C++14	100 / 100	916 ms	1144 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 2e3+5;

mt19937 rng(time(NULL));

void connect(int a, int b) {
    if(a > b) swap(a, b);
    Bridge(a, b);
}

vector<int> sub[N];

void solve(vector<int> vec) {
    if(vec.size() < 2) return;
    for(int x : vec) sub[x].clear();
    shuffle(vec.begin(), vec.end(), rng);

    int a = vec[0], b = vec[1];
    vector<int> path;
    for(int i = 2; i < vec.size(); i++) {
        int now = Query(a, b, vec[i]);
        sub[now].emplace_back(vec[i]);
        if(now == vec[i]) path.emplace_back(now);
    }
    sub[a].emplace_back(a), sub[b].emplace_back(b);
    sort(path.begin(), path.end(), [&](int x, int y) {
        return Query(x, y, b) == y;
    });
    path.insert(path.begin(), a), path.emplace_back(b);
    for(int i = 0; i < path.size() - 1; i++)
        connect(path[i], path[i + 1]);

    for(int x : path) solve(sub[x]);
}

void Solve(int n) {
    vector<int> vec;
    for(int i = 0; i < n; i++) vec.emplace_back(i);
    solve(vec);
}

Compilation message (stderr)

meetings.cpp: In function 'void solve(std::vector<int>)':
meetings.cpp:24:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 2; i < vec.size(); i++) {
                    ~~^~~~~~~~~~~~
meetings.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < path.size() - 1; i++)
                    ~~^~~~~~~~~~~~~~~~~

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