Submission #230101

#	Time	Username	Problem	Language	Result	Execution time	Memory
230101		PeppaPig	Meetings (JOI19_meetings)	C++14	100 / 100	943 ms	1068 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
 
#define pii pair<int, int>
#define x first
#define y second
 
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);
}
 
void solve(vector<int> &vec) {
    if(vec.size() <= 2) {
        if(vec.size() == 2) connect(vec[0], vec[1]);
        return;
    }
    shuffle(vec.begin(), vec.end(), rng);
    int a = vec[0], b = vec[1];
    map<int, vector<int> > mp;
    for(int i = 2; i < vec.size(); i++) {
        int now = Query(a, b, vec[i]);
        mp[now].emplace_back(vec[i]);
    }
    vector<int> path;
    for(auto p : mp) {
        if(p.x == a) p.y.emplace_back(a);
        else if(p.x == b) p.y.emplace_back(b);
        else path.emplace_back(p.x);
        solve(p.y);
    }
    sort(path.begin(), path.end(), [&](int x, int y) {
        return Query(x, y, b) == y;
    });
    if(!path.empty()) {
        connect(a, path[0]), connect(path.back(), b);
        for(int i = 0; i < path.size() - 1; i++) connect(path[i], path[i + 1]);
    } else connect(a, b);
}
 
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:27:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 2; i < vec.size(); i++) {
                    ~~^~~~~~~~~~~~
meetings.cpp:43:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < path.size() - 1; i++) connect(path[i], path[i + 1]);
                        ~~^~~~~~~~~~~~~~~~~

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