This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
void bridge(int u, int v) {
if (u > v) swap(u, v);
Bridge(u, v);
}
void solve(vector<int> &T) {
if (T.size() <= 1)
return;
if (T.size() == 2) {
bridge(T[0], T[1]);
return;
}
vector<int> path;
map<int, vector<int>> S;
for (int i = 2; i < T.size(); ++i) {
int q = Query(T[0], T[1], T[i]);
if (q != T[0] || q != T[1]) path.push_back(q);
S[q].push_back(T[i]);
}
sort(path.begin(), path.end());
path.resize(unique(path.begin(), path.end()) - path.begin());
S[T[0]].push_back(T[0]);
S[T[1]].push_back(T[1]);
for (auto [u, T0]: S) solve(T0);
sort(path.begin(), path.end(), [&](int u, int v) {return Query(T[0], u, v) == u;});
path.insert(path.begin(), T[0]);
path.push_back(T[1]);
for (int i = 1; i < path.size(); ++i) {
bridge(path[i], path[i - 1]);
}
}
void Solve(int32_t n){
srand(time(NULL));
vector<int> nodes(n);
iota(nodes.begin(), nodes.end(), 0);
mt19937 rng((int64_t) new char);
shuffle(nodes.begin(), nodes.end(), rng);
solve(nodes);
}
Compilation message (stderr)
meetings.cpp: In function 'void solve(std::vector<int>&)':
meetings.cpp:20:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for (int i = 2; i < T.size(); ++i) {
| ~~^~~~~~~~~~
meetings.cpp:35:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for (int i = 1; i < path.size(); ++i) {
| ~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |