#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
inline void myBridge(int x, int y) {
if(x > y) swap(x, y);
//cerr << x << " " << y << "\n";
Bridge(x, y);
}
void solve(vector <int> &nodes, int par) {
int n = nodes.size();
if(n == 1) {
myBridge(par, nodes[0]);
n--;
}
if(n == 0) return ;
vector < pair <int, int> > arr;
vector <int> path;
int nod = nodes[rand() % n];
for(auto it : nodes) {
if(it == nod) continue;
int cur = Query(par, it, nod);
if(cur == it) {
if(cur != par && cur != nod)
path.push_back(cur);
}
else {
arr.push_back({cur, it});
}
}
sort(path.begin(), path.end());
path.resize(unique(path.begin(), path.end()) - path.begin());
/*cerr << par << " " << nod << "\n";
for(auto it : arr) {
cerr << it.second << " ";
}
cerr << "\n";*/
if(path.empty()) {
myBridge(par, nod);
}
else {
sort(path.begin(), path.end(), [&](const int &x, const int &y) {
return Query(par, x, y) == x;
});
myBridge(par, path[0]);
for(int i = 0; i + 1 < path.size(); i++) {
myBridge(path[i], path[i + 1]);
}
myBridge(path.back(), nod);
}
int i = 0;
while(i < arr.size()) {
vector <int> aux;
int j = i;
while(j < arr.size() && arr[i].first == arr[j].first) {
aux.push_back(arr[j].second);
j++;
}
solve(aux, arr[i].first);
//cerr << j << " " << arr.size() << "\n";
i = j;
}
}
void Solve(int n) {
srand(time(NULL));
vector <int> nodes(n - 1);
iota(nodes.begin(), nodes.end(), 1);
solve(nodes, 0);
}
Compilation message
meetings.cpp: In function 'void solve(std::vector<int>&, int)':
meetings.cpp:51:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i + 1 < path.size(); i++) {
~~~~~~^~~~~~~~~~~~~
meetings.cpp:58:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(i < arr.size()) {
~~^~~~~~~~~~~~
meetings.cpp:61:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < arr.size() && arr[i].first == arr[j].first) {
~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
244 KB |
Output is correct |
5 |
Correct |
2 ms |
248 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
248 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
360 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
248 KB |
Output is correct |
12 |
Correct |
2 ms |
296 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
244 KB |
Output is correct |
5 |
Correct |
2 ms |
248 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
248 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
360 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
248 KB |
Output is correct |
12 |
Correct |
2 ms |
296 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
14 |
Incorrect |
2 ms |
248 KB |
Wrong Answer [4] |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
380 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
2 ms |
248 KB |
Output is correct |
4 |
Correct |
2 ms |
244 KB |
Output is correct |
5 |
Correct |
2 ms |
248 KB |
Output is correct |
6 |
Correct |
2 ms |
376 KB |
Output is correct |
7 |
Correct |
2 ms |
248 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
360 KB |
Output is correct |
10 |
Correct |
2 ms |
248 KB |
Output is correct |
11 |
Correct |
2 ms |
248 KB |
Output is correct |
12 |
Correct |
2 ms |
296 KB |
Output is correct |
13 |
Correct |
2 ms |
248 KB |
Output is correct |
14 |
Incorrect |
2 ms |
248 KB |
Wrong Answer [4] |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
82 ms |
536 KB |
Wrong Answer [4] |
2 |
Halted |
0 ms |
0 KB |
- |